एल अंकन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Notation describing limiting behavior in computational number theory}} | {{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 10: | Line 9: | ||
जहाँ 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>\alpha</math> 0 है, तो | कब <math>\alpha</math> 0 है, तो | ||
| Line 22: | Line 21: | ||
ln n का पूर्ण चरघातांकी फलन है (और इस प्रकार n में बहुपद)। | 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>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> | :<math>L_n[1/2, 1] = e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,</math> | ||
| Line 42: | Line 41: | ||
== इतिहास == | == इतिहास == | ||
एल-संकेतन को पूरे साहित्य में विभिन्न रूपों में परिभाषित किया गया है। इसका पहला प्रयोग कार्ल पोमेरेन्स ने अपने पेपर "एनालिसिस एंड कंपेरिजन ऑफ सम इंटीजर कारक एल्गोरिद्म" में किया।<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> | एल-संकेतन को पूरे साहित्य में विभिन्न रूपों में परिभाषित किया गया है। इसका पहला प्रयोग कार्ल पोमेरेन्स ने अपने पेपर "एनालिसिस एंड कंपेरिजन ऑफ सम इंटीजर कारक एल्गोरिद्म" में किया।<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 name=":0">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> सुझाव देगा कि चलने का समय ऊपरी सीमा है। चूँकि , पूर्णांक कारक और असतत लॉगरिदम एल्गोरिदम के लिए जो सामान्यतः एल-संकेतन के लिए उपयोग किया जाता है, चलने का समय ऊपरी सीमा नहीं है, इसलिए यह परिभाषा पसंद नहीं की जाती है। | ||
'''त में एल्गोरिदम पर अपने लेख में दो मापदंडों को | '''त में एल्गोरिदम पर अपने लेख में दो मापदंडों को''' | ||
==संदर्भ == | ==संदर्भ == | ||
Revision as of 09:27, 20 June 2023
एल-संकेतन बिग-ओ संकेतन के अनुरूप एक स्पर्शोन्मुख संकेतन है जिसे के रूप में निरूपित किया जाता है, जो एक बाध्य चर के लिए अनंत की ओर जाता है। बड़े-ओ संकेतन की तरह यह सामान्यतः किसी विशेष एल्गोरिदम की कम्प्यूटेशनल जटिलता जैसे फलन के विकास की दर को मोटे रूप से व्यक्त करने के लिए उपयोग किया जाता है।
परिभाषा
इसे के रूप में परिभाषित किया गया है
जहाँ c एक धनात्मक स्थिरांक है और एक स्थिरांक है।
एल-संकेतन का उपयोग अधिकत्तर कम्प्यूटेशनल संख्या सिद्धांत में किया जाता है कठिन संख्या सिद्धांत समस्याओं के लिए एल्गोरिदम की जटिलता को व्यक्त करने के लिए, उदा। पूर्णांक गुणनखंडन के लिए सिव्स सिद्धांत और असतत लघुगणक को हल करने के विधि इस संकेतन का लाभ यह है कि यह इन एल्गोरिदम के विश्लेषण को सरल करता है। h> प्रमुख शब्द को व्यक्त करता है और हर छोटी चीज का ख्याल रखता है।
कब 0 है, तो
एक बहुलगणकीय फलन है (ln n का बहुपद फलन);
जब 1 है तो
ln n का पूर्ण चरघातांकी फलन है (और इस प्रकार n में बहुपद)।
यदि 0 और 1 के बीच है फलन ln (और अधिबहुपद ) का उप-घातीय समय है।
उदाहरण
कई सामान्य-उद्देश्य पूर्णांक गुणनखंड एल्गोरिदम में समय जटिलता या उप-घातीय समय होता है। सबसे अच्छा सामान्य संख्या क्षेत्र सीव है जिसका चलने का समय अपेक्षित है
लगभग के लिए नंबर क्षेत्र सीव से पहले इस तरह का सबसे अच्छा एल्गोरिथ्म द्विघात सीव था जिसमें चलने का समय होता है
अण्डाकार वक्र असतत लघुगणक समस्या के लिए सबसे तेज़ सामान्य प्रयोजन एल्गोरिथ्म बेबी-स्टेप विशाल-चरण एल्गोरिथ्म है, जिसमें समूह क्रम n के वर्ग-मूल के क्रम पर चलने का समय है। एल-संकेतन में यह होगा
एकेएस प्रारंभिक परीक्षण का अस्तित्व जो बहुपद समय में चलता ह का अर्थ है कि प्रारंभिक परीक्षण के लिए समय की जटिलता सबसे अधिक ज्ञात है
जहाँ c अधिक से अधिक 6 सिद्ध हुआ है।[1]
इतिहास
एल-संकेतन को पूरे साहित्य में विभिन्न रूपों में परिभाषित किया गया है। इसका पहला प्रयोग कार्ल पोमेरेन्स ने अपने पेपर "एनालिसिस एंड कंपेरिजन ऑफ सम इंटीजर कारक एल्गोरिद्म" में किया।[2] इस प्रपत्र में केवल पैरामीटर था: सूत्र में उस एल्गोरिथम के लिए था जिसका वह विश्लेषण कर रहा था। पोमेरेन्स इस और पिछले पत्रों में अक्षर (या लोअर केस ) का उपयोग उन सूत्रों के लिए कर रहा था जिनमें कई लघुगणक सम्मिलित थे।
अर्जेन लेनस्ट्रा और हेनरी लेनस्ट्रा द्वारा संख्या सिद्धांत में एल्गोरिदम पर अपने लेख में दो मापदंडों को सम्मिलित करने वाला सूत्र प्रस्तुत किया गया था।[3] यह डॉन कॉपरस्मिथ के असतत लघुगणक एल्गोरिथम के उनके विश्लेषण में प्रस्तुत किया गया था। यह आज साहित्य में सबसे अधिक उपयोग किया जाने वाला रूप है।
एप्लाइड क्रिप्टोग्राफी की पुस्तिका इस लेख में प्रस्तुत सूत्र के चारों ओर एक बड़े के साथ एल-संकेतन को परिभाषित करती है।[4] यह मानक परिभाषा नहीं है। बिग सुझाव देगा कि चलने का समय ऊपरी सीमा है। चूँकि , पूर्णांक कारक और असतत लॉगरिदम एल्गोरिदम के लिए जो सामान्यतः एल-संकेतन के लिए उपयोग किया जाता है, चलने का समय ऊपरी सीमा नहीं है, इसलिए यह परिभाषा पसंद नहीं की जाती है।
त में एल्गोरिदम पर अपने लेख में दो मापदंडों को
संदर्भ
- ↑ 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/.
