एसिम्प्टोटिक विश्लेषण
एसिम्प्टोटिक विश्लेषण यह बताता है कि किसी एल्गोरिथम का चलने का समय या मेमोरी कैसे बढ़ती है जब इनपुट का आकार बड़ा हो जाता है, जिसमें बिग-ओ, बिग-ओमेगा और बिग-थीटा जैसे नोटेशन का उपयोग करके विकास दर को दर्शाया जाता है, जबकि स्थिरांक और निम्न-क्रम के पदों को अनदेखा किया जाता है।
Definition
एसिम्प्टोटिक विश्लेषण किसी फ़ंक्शन की विकास दर का लक्षण वर्णन है क्योंकि इसका तर्क अनंत की ओर प्रवृत्त होता है; एल्गोरिथम विश्लेषण में यह व्यक्त करता है कि समय या स्थान का उपयोग इनपुट आकार के साथ कैसे बढ़ता है, जिसमें ऑर्डर नोटेशन का उपयोग किया जाता है जो स्थिरांक कारकों और निम्न-क्रम के पदों को दबाता है।
Scope
यह विषय संसाधन उपयोग को दर्शाने के लिए उपयोग किए जाने वाले एसिम्प्टोटिक नोटेशन — बिग-ओ (ऊपरी सीमा), बिग-ओमेगा (निचली सीमा), बिग-थीटा (सटीक सीमा), और सख्त लिटिल-ओ और लिटिल-ओमेगा — के साथ-साथ मानक विकास वर्गों (स्थिर, लघुगणकीय, रैखिक, लीनियरिथमिक, बहुपद, घातीय) और इन सीमाओं में हेरफेर के नियमों को शामिल करता है। यह बताता है कि स्थिरांक कारक और निम्न-क्रम के पदों को क्यों अमूर्त किया जाता है और एसिम्प्टोटिक तुलनाएं स्केलिंग व्यवहार की भविष्यवाणी कैसे करती हैं। इसमें इन सीमाओं को प्राप्त करने के लिए उपयोग की जाने वाली पुनरावृत्ति-समाधान मशीनरी शामिल नहीं है, जिसे अलग से कवर किया गया है।
Core questions
- बिग-ओ, बिग-ओमेगा और बिग-थीटा प्रत्येक एक फ़ंक्शन के विकास के बारे में क्या दावा करते हैं?
- एसिम्प्टोटिक तुलना में स्थिरांक कारकों और निम्न-क्रम के पदों को क्यों अनदेखा किया जाता है?
- सामान्य विकास वर्गों को सबसे धीमी से सबसे तेज़-बढ़ने वाले क्रम में कैसे व्यवस्थित किया जाता है?
- एसिम्प्टोटिक सीमाएं कैसे भविष्यवाणी करती हैं कि एक एल्गोरिथम बड़े इनपुट के लिए कैसे स्केल करता है?
- व्यवहार में एसिम्प्टोटिक रूप से धीमे एल्गोरिदम कब अभी भी बेहतर हो सकते हैं?
Key concepts
- बिग-ओ नोटेशन
- बिग-ओमेगा नोटेशन
- बिग-थीटा नोटेशन
- लिटिल-ओ और लिटिल-ओमेगा
- विकास वर्ग
- स्थिरांक कारक
- निम्न-क्रम के पद
- स्केलेबिलिटी
Key theories
- ऑर्डर नोटेशन
- बिग-ओ एक फ़ंक्शन को एक स्थिरांक कारक के भीतर ऊपर से बांधता है, बिग-ओमेगा इसे नीचे से बांधता है, और बिग-थीटा इसे दोनों तरीकों से बांधता है; कंप्यूटर विज्ञान के लिए नुथ द्वारा मानकीकृत ये परिभाषाएं, विकास दरों के लिए एक सटीक भाषा प्रदान करती हैं।
- विकास दरों का प्रभुत्व
- जैसे-जैसे इनपुट का आकार बढ़ता है, उच्च-क्रम के पद हावी होते हैं, इसलिए एक एल्गोरिथम का एसिम्प्टोटिक वर्ग (जैसे लीनियरिथमिक बनाम क्वाड्रेटिक) अंततः स्थिरांक कारकों की परवाह किए बिना इसकी स्केलेबिलिटी निर्धारित करता है।
Clinical relevance
एसिम्प्टोटिक नोटेशन एल्गोरिथम दक्षता पर चर्चा करने के लिए एक सामान्य भाषा है: यह इंजीनियरों को उम्मीदवार एल्गोरिदम की तुलना करने, यह भविष्यवाणी करने की अनुमति देता है कि क्या एक सिस्टम बड़े वर्कलोड के लिए स्केल करेगा, और प्रलेखन, साक्षात्कारों और पुस्तकालयों और मानकों के विश्लेषण में प्रदर्शन गारंटी को संप्रेषित करेगा।
History
बिग-ओ और संबंधित नोटेशन 19वीं सदी के विश्लेषणात्मक संख्या सिद्धांत में बाचमैन और लैंडौ के साथ उत्पन्न हुए (इसलिए 'लैंडौ नोटेशन')। डोनाल्ड नुथ ने 1960 और 1970 के दशक में एल्गोरिदम के विश्लेषण के लिए उन्हें अनुकूलित और मानकीकृत किया, जिसमें 1976 का एक नोट भी शामिल था जिसमें कंप्यूटर विज्ञान में बिग-ओमेगा और बिग-थीटा के उपयोग को स्पष्ट किया गया था।
Key figures
- Donald Knuth
- Paul Bachmann
- Edmund Landau
Related topics
Seminal works
- knuth1976bigo
- cormen2009
Frequently asked questions
- क्या एक छोटा बिग-ओ हमेशा एक तेज़ एल्गोरिथम का मतलब होता है?
- किसी दिए गए इनपुट आकार के लिए आवश्यक नहीं है। बिग-ओ इनपुट आकार के अनंत की ओर प्रवृत्त होने पर विकास का वर्णन करता है और स्थिरांक कारकों को छुपाता है, इसलिए एक बदतर एसिम्प्टोटिक वर्ग वाला एल्गोरिथम छोटे इनपुट पर तेज़ हो सकता है। यह बड़े इनपुट और स्केलेबिलिटी के लिए बेहतर मार्गदर्शक है।
- बिग-ओ और बिग-थीटा में क्या अंतर है?
- बिग-ओ केवल विकास पर एक ऊपरी सीमा देता है, इसलिए यह बताता है कि एल्गोरिथम एक दी गई दर से बुरा नहीं है। बिग-थीटा एक सटीक सीमा देता है, यह दावा करते हुए कि विकास उस दर से ऊपर और नीचे दोनों से मेल खाता है। यह कहना कि एक एल्गोरिथम थीटा(n log n) है, ओ(n log n) की तुलना में एक मजबूत, अधिक सटीक कथन है।