एल अंकन: Difference between revisions

Revision as of 09:02, 20 June 2023

एल-संकेतन बिग-ओ संकेतन के अनुरूप एक स्पर्शोन्मुख संकेतन है जिसे $L_{n}[\alpha ,c]$ के रूप में निरूपित किया जाता है, जो एक बाध्य चर $n$ के लिए अनंत की ओर जाता है। बड़े-ओ संकेतन की तरह यह सामान्यतः किसी विशेष एल्गोरिदम की कम्प्यूटेशनल जटिलता जैसे फलन के विकास की दर को मोटे रूप से व्यक्त करने के लिए उपयोग किया जाता है।

परिभाषा

इसे के रूप में परिभाषित किया गया है

L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}

जहाँ c एक धनात्मक स्थिरांक है और $\alpha$ एक स्थिरांक $0\leq \alpha \leq 1$ है।

एल-संकेतन का उपयोग अधिकत्तर कम्प्यूटेशनल संख्या सिद्धांत में किया जाता है कठिन संख्या सिद्धांत समस्याओं के लिए एल्गोरिदम की जटिलता को व्यक्त करने के लिए, उदा। पूर्णांक गुणनखंडन के लिए सिव्स सिद्धांत और असतत लघुगणक को हल करने के विधि इस संकेतन का लाभ यह है कि यह इन एल्गोरिदम के विश्लेषण को सरल करता है। $e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ h> प्रमुख शब्द को व्यक्त करता है और $e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ हर छोटी चीज का ख्याल रखता है।

कब $\alpha$ 0 है, तो

L_{n}[\alpha ,c]=L_{n}[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}\,

एक बहुलगणकीय फलन है (ln n का बहुपद फलन);

जब $\alpha$ 1 है तो

L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}\,

ln n का पूर्ण चरघातांकी फलन है (और इस प्रकार n में बहुपद)।

यदि $\alpha$ 0 और 1 के बीच है फलन ln (और अधिबहुपद ) का उप-घातीय समय है।

उदाहरण

कई सामान्य-उद्देश्य पूर्णांक गुणनखंड एल्गोरिदम में समय जटिलता या उप-घातीय समय होता है। सबसे अच्छा सामान्य संख्या क्षेत्र सीव है जिसका चलने का समय अपेक्षित है

L_{n}[1/3,c]=e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}

लगभग $c=(64/9)^{1/3}\approx 1.923$ के लिए नंबर क्षेत्र सीव से पहले इस तरह का सबसे अच्छा एल्गोरिथ्म द्विघात सीव था जिसमें चलने का समय होता है

L_{n}[1/2,1]=e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,

अण्डाकार वक्र असतत लघुगणक समस्या के लिए सबसे तेज़ सामान्य प्रयोजन एल्गोरिथ्म बेबी-स्टेप विशाल-चरण एल्गोरिथ्म है, जिसमें समूह क्रम n के वर्ग-मूल के क्रम पर चलने का समय है। एल-संकेतन में यह होगा

L_{n}[1,1/2]=n^{1/2+o(1)}.\,

एकेएस प्रारंभिक परीक्षण का अस्तित्व जो बहुपद समय में चलता ह का अर्थ है कि प्रारंभिक परीक्षण के लिए समय की जटिलता सबसे अधिक ज्ञात है

L_{n}[0,c]=(\ln n)^{c+o(1)}\,

जहाँ c अधिक से अधिक 6 सिद्ध हुआ है।^[1]

इतिहास

एल-संकेतन को पूरे साहित्य में विभिन्न रूपों में परिभाषित किया गया है। इसका पहला प्रयोग कार्ल पोमेरेन्स ने अपने पेपर "एनालिसिस एंड कंपेरिजन ऑफ सम इंटीजर कारक एल्गोरिद्म" में किया।^[2] इस प्रपत्र में केवल $c$ पैरामीटर था: सूत्र में $\alpha$ उस एल्गोरिथम के लिए $1/2$ था जिसका वह विश्लेषण कर रहा था। पोमेरेन्स इस और पिछले पत्रों में $L$ अक्षर (या लोअर केस $l$ ) का उपयोग उन सूत्रों के लिए कर रहा था जिनमें कई लघुगणक सम्मिलित थे।

अर्जेन लेनस्ट्रा और हेनरी लेनस्ट्रा द्वारा संख्या सिद्धांत में एल्गोरिदम पर अपने लेख में दो मापदंडों को सम्मिलित करने वाला सूत्र प्रस्तुत किया गया था।^[3] यह डॉन कॉपरस्मिथ के असतत लघुगणक एल्गोरिथम के उनके विश्लेषण में प्रस्तुत किया गया था। यह आज साहित्य में सबसे अधिक उपयोग किया जाने वाला रूप है।

एप्लाइड क्रिप्टोग्राफी की पुस्तिका इस लेख में प्रस्तुत सूत्र के चारों ओर एक बड़े $O$ के साथ एल-संकेतन को परिभाषित करती है।^[4] यह मानक परिभाषा नहीं है। बिग $O$ सुझाव देगा कि चलने का समय ऊपरी सीमा है। चूँकि , पूर्णांक कारक और असतत लॉगरिदम एल्गोरिदम के लिए जो सामान्यतः एल-संकेतन के लिए उपयोग किया जाता है, चलने का समय ऊपरी सीमा नहीं है, इसलिए यह परिभाषा पसंद नहीं की जाती है।

संदर्भ

↑ Hendrik W. Lenstra Jr. and Carl Pomerance, "Primality testing with Gaussian periods", preprint, 2011, http://www.math.dartmouth.edu/~carlp/aks041411.pdf.
↑ Carl Pomerance, "Analysis and comparison of some integer factoring algorithms", In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982, http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf
↑ Arjen K. Lenstra and Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991.
↑ Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. ISBN 0-8493-8523-7. http://www.cacr.math.uwaterloo.ca/hac/.

[1] Hendrik W. Lenstra Jr. and Carl Pomerance, "Primality testing with Gaussian periods", preprint, 2011, http://www.math.dartmouth.edu/~carlp/aks041411.pdf.

[2] Carl Pomerance, "Analysis and comparison of some integer factoring algorithms", In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982, http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf

[3] Arjen K. Lenstra and Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991.

[4] Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. ISBN 0-8493-8523-7. http://www.cacr.math.uwaterloo.ca/hac/.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
 {{Short description|Notation describing limiting behavior in computational number theory}}
-''एल''-संकेतन बिग-ओ अंकन के अनुरूप एक [[स्पर्शोन्मुख विश्लेषण]] संकेतन है, जिसे इस रूप में दर्शाया गया है <math>L_n[\alpha,c]</math> एक [[बाध्य चर]] के लिए <math>n</math> [[सीमा (गणित)]]। बिग-ओ नोटेशन की तरह, यह आमतौर पर किसी फ़ंक्शन (गणित) के विकास की दर को व्यक्त करने के लिए उपयोग किया जाता है, जैसे किसी विशेष [[कलन विधि]] के [[कम्प्यूटेशनल जटिलता सिद्धांत]]।
+एल-संकेतन बिग-ओ संकेतन के अनुरूप एक स्पर्शोन्मुख संकेतन है जिसे <math>L_n[\alpha,c]</math> के रूप में निरूपित किया जाता है, जो एक [[बाध्य चर]] <math>n</math> के लिए अनंत की ओर जाता है। बड़े-ओ संकेतन की तरह यह सामान्यतः किसी विशेष एल्गोरिदम की कम्प्यूटेशनल जटिलता जैसे फलन के विकास की दर को मोटे रूप से  व्यक्त करने के लिए उपयोग किया जाता है।
 == परिभाषा ==
@@ Line 6: / Line 8: @@
 :<math>L_n[\alpha,c]=e^{(c+o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math>
-जहाँ c एक सकारात्मक स्थिरांक है, और <math>\alpha</math> एक स्थिरांक है <math>0 \leq \alpha \leq 1</math>.
+जहाँ c एक धनात्मक स्थिरांक है और <math>\alpha</math> एक स्थिरांक <math>0 \leq \alpha \leq 1</math> है।
+एल-संकेतन का उपयोग अधिकत्तर कम्प्यूटेशनल [[संख्या सिद्धांत]] में किया जाता है कठिन संख्या सिद्धांत समस्याओं के लिए एल्गोरिदम की जटिलता को व्यक्त करने के लिए, उदा। [[पूर्णांक गुणनखंडन]] के लिए सिव्स  सिद्धांत और [[असतत लघुगणक]] को हल करने के विधि इस संकेतन का लाभ यह है कि यह इन एल्गोरिदम के विश्लेषण को सरल करता है। <math>e^{c(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math> h> प्रमुख शब्द को व्यक्त करता है और  <math>e^{o(1)(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math> हर छोटी चीज का ख्याल रखता है।
-एल-नोटेशन का उपयोग ज्यादातर [[कम्प्यूटेशनल [[संख्या सिद्धांत]]]] में किया जाता है, कठिन संख्या सिद्धांत समस्याओं के लिए एल्गोरिदम की जटिलता को व्यक्त करने के लिए, उदा। [[पूर्णांक गुणनखंडन]] के लिए छलनी सिद्धांत और [[असतत लघुगणक]] को हल करने के तरीके। इस संकेतन का लाभ यह है कि यह इन एल्गोरिदम के विश्लेषण को सरल करता है। <math>e^{c(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math> h> प्रमुख शब्द को व्यक्त करता है, और  <math>e^{o(1)(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math> हर छोटी चीज का ख्याल रखता है।
-<!-- Expand this, add some math and cites, and it may be a useful addition
-Many advanced number theory algorithms have not been fully studied and not much is definitely known about their complexity and behaviour. The breadth of L-notation, allowing one to span polynomial to exponential growth rates, and its looseness, allowing theorems and heuristic analyses to be made more easily, have made its use popular in this relatively niche field.
--->
 कब <math>\alpha</math> 0 है, तो
@@ Line 17: / Line 17: @@
 एक बहुलगणकीय फलन है (ln n का बहुपद फलन);
-कब <math>\alpha</math> 1 है तो
+जब <math>\alpha</math> 1 है तो
 :<math>L_n[\alpha,c] = L_n[1, c] = e^{(c + o(1)) \ln n} = n^{c + o(1)}\,</math>
 ln n का पूर्ण चरघातांकी फलन है (और इस प्रकार n में बहुपद)।
-अगर <math>\alpha</math> 0 और 1 के बीच है, फ़ंक्शन ln (और [[ अधिबहुपद ]]) का [[उप-घातीय समय]] है।
+यदि <math>\alpha</math> 0 और 1 के बीच है फलन ln (और [[ अधिबहुपद ]]) का [[उप-घातीय समय]] है।
 == उदाहरण ==
-कई सामान्य-उद्देश्य पूर्णांक गुणनखंड एल्गोरिदम में समय जटिलता # उप-घातीय समय होता है। सबसे अच्छा [[सामान्य संख्या क्षेत्र छलनी]] है, जिसका चलने का समय अपेक्षित है
+कई सामान्य-उद्देश्य पूर्णांक गुणनखंड एल्गोरिदम में समय जटिलता या उप-घातीय समय होता है। सबसे अच्छा [[सामान्य संख्या क्षेत्र छलनी|सामान्य संख्या क्षेत्र सीव]]  है जिसका चलने का समय अपेक्षित है
 :<math>L_n[1/3, c] = e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}</math>
-के लिए <math> c = (64/9)^{1/3} \approx 1.923</math>. नंबर फील्ड छलनी से पहले इस तरह का सबसे अच्छा एल्गोरिथ्म द्विघात छलनी था जिसमें चलने का समय होता है
+लगभग <math> c = (64/9)^{1/3} \approx 1.923</math> के लिए नंबर क्षेत्र सीव  से पहले इस तरह का सबसे अच्छा एल्गोरिथ्म द्विघात सीव  था जिसमें चलने का समय होता है
 :<math>L_n[1/2, 1] = e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,</math>
-[[अण्डाकार वक्र]] असतत लघुगणक समस्या के लिए, सबसे तेज़ सामान्य प्रयोजन एल्गोरिथ्म बेबी-स्टेप विशाल-चरण एल्गोरिथ्म है, जिसमें समूह क्रम n के वर्ग-मूल के क्रम पर चलने का समय है। एल-नोटेशन में यह होगा
+[[अण्डाकार वक्र]] असतत लघुगणक समस्या के लिए सबसे तेज़ सामान्य प्रयोजन एल्गोरिथ्म बेबी-स्टेप विशाल-चरण एल्गोरिथ्म है, जिसमें समूह क्रम n के वर्ग-मूल के क्रम पर चलने का समय है। एल-संकेतन में यह होगा
 :<math>L_n[1, 1/2] = n^{1/2+o(1)}.\,</math>
-[[एकेएस [[प्रारंभिक परीक्षण]]]] का अस्तित्व, जो बहुपद समय में चलता है, का अर्थ है कि प्रारंभिक परीक्षण के लिए समय की जटिलता सबसे अधिक ज्ञात है
+एकेएस [[प्रारंभिक परीक्षण]] का अस्तित्व जो बहुपद समय में चलता ह का अर्थ है कि प्रारंभिक परीक्षण के लिए समय की जटिलता सबसे अधिक ज्ञात है
 :<math>L_n[0, c] = (\ln n)^{c+o(1)}\,</math>
@@ Line 42: / Line 42: @@
 == इतिहास ==
-एल-नोटेशन को पूरे साहित्य में विभिन्न रूपों में परिभाषित किया गया है। इसका पहला प्रयोग [[कार्ल पोमेरेन्स]] ने अपने पेपर विश्लेषण और कुछ पूर्णांक फैक्टरिंग एल्गोरिदम की तुलना में किया।<ref>Carl Pomerance, "Analysis and comparison of some integer factoring algorithms", In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982, http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf</ref> इस प्रपत्र में केवल था <math>c</math> पैरामीटर: द <math>\alpha</math> सूत्र में था <math>1/2</math> एल्गोरिदम के लिए वह विश्लेषण कर रहा था। पोमेरेन्स पत्र का उपयोग कर रहा था <math>L</math> (या लोअर केस <math>l</math>) इसमें और पिछले पत्रों में सूत्रों के लिए जिसमें कई लघुगणक शामिल हैं।
+एल-संकेतन को पूरे साहित्य में विभिन्न रूपों में परिभाषित किया गया है। इसका पहला प्रयोग कार्ल पोमेरेन्स ने अपने पेपर "एनालिसिस एंड कंपेरिजन ऑफ सम इंटीजर कारक एल्गोरिद्म" में किया।<ref>Carl Pomerance, "Analysis and comparison of some integer factoring algorithms", In Mathematisch Centrum Computational Methods in Number Theory, Part 1, pp. 89-139, 1982, http://www.math.dartmouth.edu/~carlp/PDF/analysiscomparison.pdf</ref>  इस प्रपत्र में केवल <math>c</math> पैरामीटर था: सूत्र में <math>\alpha</math> उस एल्गोरिथम के लिए <math>1/2</math> था जिसका वह विश्लेषण कर रहा था। पोमेरेन्स इस और पिछले पत्रों में <math>L</math> अक्षर (या लोअर केस <math>l</math>) का उपयोग उन सूत्रों के लिए कर रहा था जिनमें कई लघुगणक सम्मिलित  थे।
+[[अर्जेन लेनस्ट्रा]] और [[हेनरी लेनस्ट्रा]] द्वारा संख्या सिद्धांत में एल्गोरिदम पर अपने लेख में दो मापदंडों को सम्मिलित  करने वाला सूत्र प्रस्तुत किया गया था।<ref>Arjen K. Lenstra and Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991.</ref> यह [[डॉन कॉपरस्मिथ]] के असतत लघुगणक एल्गोरिथम के उनके विश्लेषण में प्रस्तुत किया गया था। यह आज साहित्य में सबसे अधिक उपयोग किया जाने वाला रूप है।
-[[अर्जेन लेनस्ट्रा]] और [[हेनरी लेनस्ट्रा]] द्वारा नंबर थ्योरी में एल्गोरिदम पर अपने लेख में दो मापदंडों को शामिल करने वाला सूत्र पेश किया गया था।<ref>Arjen K. Lenstra and Hendrik W. Lenstra, Jr, "Algorithms in Number Theory", in Handbook of Theoretical Computer Science (vol. A): Algorithms and Complexity, 1991.</ref> यह [[डॉन कॉपरस्मिथ]] के असतत लघुगणक एल्गोरिथम के उनके विश्लेषण में पेश किया गया था। यह आज साहित्य में सबसे अधिक इस्तेमाल किया जाने वाला रूप है।
-एप्लाइड क्रिप्टोग्राफी की पुस्तिका एल-नोटेशन को एक बड़े के साथ परिभाषित करती है <math>O</math> इस लेख में प्रस्तुत सूत्र के आसपास।<ref>Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. {{isbn|0-8493-8523-7}}. http://www.cacr.math.uwaterloo.ca/hac/.</ref> यह मानक परिभाषा नहीं है। बड़ा <math>O</math> सुझाव देगा कि चलने का समय ऊपरी सीमा है। हालांकि, पूर्णांक फैक्टरिंग और असतत लॉगरिदम एल्गोरिदम के लिए जो आमतौर पर एल-नोटेशन के लिए उपयोग किया जाता है, चलने का समय ऊपरी सीमा नहीं है, इसलिए यह परिभाषा पसंद नहीं की जाती है।
+एप्लाइड क्रिप्टोग्राफी की पुस्तिका इस लेख में प्रस्तुत सूत्र के चारों ओर एक बड़े <math>O</math> के साथ एल-संकेतन को परिभाषित करती है।<ref>Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996. {{isbn|0-8493-8523-7}}. http://www.cacr.math.uwaterloo.ca/hac/.</ref> यह मानक परिभाषा नहीं है। बिग <math>O</math> सुझाव देगा कि चलने का समय ऊपरी सीमा है। चूँकि , पूर्णांक कारक और असतत लॉगरिदम एल्गोरिदम के लिए जो सामान्यतः  एल-संकेतन के लिए उपयोग किया जाता है, चलने का समय ऊपरी सीमा नहीं है, इसलिए यह परिभाषा पसंद नहीं की जाती है।
 ==संदर्भ==

Anonymous

Search

एल अंकन: Difference between revisions

Namespaces

More

Page actions

Revision as of 09:02, 20 June 2023

Contents

परिभाषा

उदाहरण

इतिहास

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

एल अंकन: Difference between revisions

Revision as of 09:02, 20 June 2023

परिभाषा

उदाहरण

इतिहास

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories