एल अंकन

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