एल अंकन

एल-संकेतन बिग-ओ अंकन के अनुरूप एक स्पर्शोन्मुख विश्लेषण संकेतन है, जिसे इस रूप में दर्शाया गया है $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 सिद्ध हुआ है।

इतिहास

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

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

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