एल अंकन

एल-संकेतन बिग-ओ संकेतन के अनुरूप एक स्पर्शोन्मुख संकेतन है जिसे $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}}.\,$