एल अंकन

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

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