सर्वोत्तम, निकृष्ट और औसत अवस्था
कंप्यूटर विज्ञान में, किसी दिए गए एल्गोरिदम के सर्वोत्तम, निकृष्ट और औसत स्थिति क्रमशः यह व्यक्त करते हैं कि संसाधन का उपयोग न्यूनतम, अधिकतम और औसत पर क्या है। आम तौर पर, जिस संसाधन पर विचार किया जा रहा है वह रनिंग टाइम है, यानी समय जटिलता, लेकिन मेमोरी या कोई अन्य संसाधन भी हो सकता है। सबसे अच्छा स्थिति वह फ़ंक्शन है जो n तत्वों के इनपुट डेटा पर न्यूनतम चरणों को निष्पादित करता है। निकृष्ट स्थिति वह फ़ंक्शन है जो आकार n के इनपुट डेटा पर अधिकतम संख्या में चरण निष्पादित करता है। औसत केस वह फ़ंक्शन है जो n तत्वों के इनपुट डेटा पर औसत चरणों की संख्या निष्पादित करता है।
वास्तविक समय कंप्यूटिंग में, सबसे निकृष्ट स्थिति में निष्पादन समय अक्सर विशेष चिंता का विषय होता है क्योंकि यह जानना महत्वपूर्ण है कि निकृष्ट स्थिति में यह गारंटी देने के लिए कितने समय की आवश्यकता हो सकती है कि एल्गोरिदम हमेशा समय पर समाप्त होगा।
एल्गोरिथम विश्लेषण में औसत प्रदर्शन और निकृष्ट स्थिति वाला प्रदर्शन सबसे अधिक उपयोग किया जाता है। सबसे अच्छा प्रदर्शन प्रदर्शन कम व्यापक रूप से पाया जाता है, लेकिन इसके उपयोग भी हैं: उदाहरण के लिए, जहां व्यक्तिगत कार्यों के सर्वोत्तम स्थिति ज्ञात हैं, उनका उपयोग समग्र निकृष्ट स्थिति विश्लेषण की सटीकता में सुधार करने के लिए किया जा सकता है। अपेक्षित चलने का समय निर्धारित करने के लिए कंप्यूटर वैज्ञानिक संभाव्य विश्लेषण तकनीकों, विशेष रूप से अपेक्षित मूल्य का उपयोग करते हैं।
इन शब्दों का प्रयोग अन्य सन्दर्भों में किया जाता है; उदाहरण के लिए किसी महामारी का सबसे खराब और सबसे अच्छा परिणाम, निकृष्ट स्थिति वाला तापमान जिसके संपर्क में कोई इलेक्ट्रॉनिक सर्किट घटक आता है, आदि। जहां निर्दिष्ट सहिष्णुता के घटकों का उपयोग किया जाता है, उपकरणों को सहनशीलता और बाहरी परिस्थितियों के निकृष्ट स्थिति संयोजन के साथ ठीक से काम करने के लिए डिज़ाइन किया जाना चाहिए।
एल्गोरिथम के लिए सर्वोत्तम-स्थिति प्रदर्शन
सर्वोत्तम-स्थिति प्रदर्शन शब्द का इस्तेमाल कंप्यूटर विज्ञान में इष्टतम परिस्थितियों में एल्गोरिदम के व्यवहार का वर्णन करने के लिए किया जाता है। उदाहरण के लिए, किसी सूची पर सरल रैखिक खोज का सर्वोत्तम स्थिति तब होता है जब वांछित तत्व सूची का पहला तत्व होता है।
एल्गोरिदम का विकास और चयन शायद ही कभी सर्वोत्तम-स्थिति के प्रदर्शन पर आधारित होता है: अधिकांश शैक्षणिक और वाणिज्यिक उद्यम औसत-स्थिति की जटिलता और सबसे खराब-स्थिति के प्रदर्शन में सुधार करने में अधिक रुचि रखते हैं। इनपुट के एक सीमित सेट के लिए हार्ड-कोडिंग समाधानों द्वारा अच्छे सर्वोत्तम-स्थिति में चलने के समय के लिए एल्गोरिदम को भी मामूली रूप से संशोधित किया जा सकता है, जिससे माप लगभग अर्थहीन हो जाता है।[1]
निकृष्ट स्थिति बनाम परिशोधित बनाम औसत-स्थिति प्रदर्शन
निकृष्ट स्थिति के प्रदर्शन विश्लेषण और औसत-मामले के प्रदर्शन विश्लेषण में कुछ समानताएं हैं, लेकिन व्यवहार में आमतौर पर अलग-अलग टूल और दृष्टिकोण की आवश्यकता होती है।
विशिष्ट इनपुट का क्या मतलब है यह निर्धारित करना कठिन है, और अक्सर उस औसत इनपुट में ऐसे गुण होते हैं जो गणितीय रूप से वर्णन करना कठिन बनाते हैं (उदाहरण के लिए, एल्गोरिदम पर विचार करें जो पाठ के स्ट्रिंग पर काम करने के लिए डिज़ाइन किए गए हैं)। इसी तरह, जब किसी विशेष "औसत मामले" (जो संभवतः केवल एल्गोरिथ्म के कुछ उपयोगों के लिए लागू होगा) का एक समझदार विवरण संभव है, तो उनके परिणामस्वरूप समीकरणों का अधिक कठिन विश्लेषण होता है।[2]
निकृष्ट स्थिति का विश्लेषण एक सुरक्षित विश्लेषण देता है (निकृष्ट स्थिति को कभी भी कम करके नहीं आंका जाता है), लेकिन ऐसा विश्लेषण जो अत्यधिक निराशावादी हो सकता है, क्योंकि ऐसा कोई (यथार्थवादी) इनपुट नहीं हो सकता है जो इतने कदम उठाएगा।
कुछ परिस्थितियों में सुरक्षा की गारंटी के लिए निराशावादी विश्लेषण का उपयोग करना आवश्यक हो सकता है। हालाँकि, अक्सर एक निराशावादी विश्लेषण बहुत अधिक निराशावादी हो सकता है, इसलिए एक विश्लेषण जो वास्तविक मूल्य के करीब पहुँचता है लेकिन आशावादी हो सकता है (शायद विफलता की कुछ ज्ञात कम संभावना के साथ) अधिक व्यावहारिक दृष्टिकोण हो सकता है। अकादमिक सिद्धांत में निकृष्ट स्थिति और औसत-मामले विश्लेषण के बीच अंतर को पाटने के एक आधुनिक दृष्टिकोण को सहज विश्लेषण कहा जाता है।
एल्गोरिदम का विश्लेषण करते समय, जिसे पूरा होने में अक्सर थोड़ा समय लगता है, लेकिन समय-समय पर बहुत अधिक समय की आवश्यकता होती है, संचालन की श्रृंखला (संभवतः अनंत) पर निकृष्ट स्थिति में चलने का समय निर्धारित करने के लिए परिशोधन विश्लेषण का उपयोग किया जा सकता है। यह परिशोधन लागत औसत लागत के बहुत करीब हो सकती है, जबकि अभी भी चलने के समय पर एक गारंटीकृत ऊपरी सीमा प्रदान की जाती है। तो उदा. ऑनलाइन एल्गोरिदम अक्सर अमूर्त विश्लेषण पर आधारित होते हैं।
निकृष्ट स्थिति का विश्लेषण निकृष्ट स्थिति की जटिलता से संबंधित है।[3]
व्यावहारिक परिणाम
खराब निकृष्ट स्थिति वाले प्रदर्शन वाले कई एल्गोरिदम का औसत-स्थिति प्रदर्शन अच्छा होता है। जिन समस्याओं को हम हल करना चाहते हैं, उनके लिए यह एक अच्छी बात है: हम आशा कर सकते हैं कि जिन विशेष उदाहरणों की हमें परवाह है वे औसत हों। क्रिप्टोग्राफी के लिए, यह बहुत खराब है: हम चाहते हैं कि क्रिप्टोग्राफ़िक समस्या के विशिष्ट उदाहरण कठिन हों। यहां कुछ विशिष्ट समस्याओं के लिए रैंडम सेल्फ-रिड्यूसिबिलिटी जैसी विधियों का उपयोग यह दिखाने के लिए किया जा सकता है कि सबसे खराब मामला औसत मामले की तुलना में कठिन नहीं है, या, समकक्ष, कि औसत मामला सबसे खराब मामले की तुलना में आसान नहीं है।
दूसरी ओर, हैश टेबल जैसी कुछ डेटा संरचनाओं में निकृष्ट स्थिति वाला व्यवहार बहुत खराब होता है, लेकिन पर्याप्त आकार की एक अच्छी तरह से लिखी गई हैश टेबल सांख्यिकीय रूप से कभी भी निकृष्ट स्थिति नहीं देगी; किए गए ऑपरेशनों की औसत संख्या एक घातांकीय क्षय वक्र का अनुसरण करती है, और इसलिए किसी ऑपरेशन का रन टाइम सांख्यिकीय रूप से सीमित होता है।
उदाहरण
सॉर्टिंग एल्गोरिदम
| Algorithm | Data structure | Time complexity:Best | Time complexity:Average | Time complexity:Worst | Space complexity:Worst |
|---|---|---|---|---|---|
| Quick sort | Array | O(n log(n)) | O(n log(n)) | O(n2) | O(n) |
| Merge sort | Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| Heap sort | Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| Smooth sort | Array | O(n) | O(n log(n)) | O(n log(n)) | O(1) |
| Bubble sort | Array | O(n) | O(n2) | O(n2) | O(1) |
| Insertion sort | Array | O(n) | O(n2) | O(n2) | O(1) |
| Selection sort | Array | O(n2) | O(n2) | O(n2) | O(1) |
| Bogo sort | Array | O(n) | O(n n!) | O(∞) | O(1) |
* सम्मिलन सॉर्ट को n तत्वों की सूची पर लागू किया जाता है, जिसे सभी अलग-अलग और प्रारंभ में यादृच्छिक क्रम में माना जाता है। औसतन, सूची ए में आधे तत्व1 ... एj तत्व A से कम हैंj+1, और आधे बड़े हैं। इसलिए, एल्गोरिदम (j + 1) की तुलना करता हैवेंतत्व को पहले से ही क्रमबद्ध उप-सूची के आधे के साथ औसतन डाला जाना है, इसलिए टीj = जे/2. परिणामी औसत-केस रनिंग टाइम पर काम करने से निकृष्ट स्थिति वाले रनिंग टाइम की तरह, इनपुट आकार का एक द्विघात फ़ंक्शन प्राप्त होता है।
- जल्दी से सुलझाएं को n तत्वों की सूची पर लागू किया गया, फिर से सभी को अलग-अलग और प्रारंभ में यादृच्छिक क्रम में माना गया। इस लोकप्रिय छँटाई एल्गोरिथ्म का औसत-केस प्रदर्शन O(n log(n)) है, जो इसे व्यवहार में बहुत तेज़ एल्गोरिदम बनाने में योगदान देता है। लेकिन निकृष्ट स्थिति वाले इनपुट को देखते हुए, इसका प्रदर्शन घटकर O(n) हो जाता है2). साथ ही, जब सबसे छोटी पहली नीति के साथ कार्यान्वित किया जाता है, तो निकृष्ट स्थिति वाली स्थान जटिलता O(log(n)) से बंधी होती है।
- हीपसॉर्ट में O(n) समय होता है जब सभी तत्व समान होते हैं। हीपिफाई में O(n) समय लगता है और फिर ढेर से तत्वों को हटाने में प्रत्येक n तत्व के लिए O(1) समय लगता है। यदि सभी तत्व अलग-अलग होने चाहिए तो रन टाइम बढ़कर O(nlog(n)) हो जाता है।
- बोगोसोर्ट में O(n) समय होता है जब तत्वों को पहले पुनरावृत्ति पर क्रमबद्ध किया जाता है। प्रत्येक पुनरावृत्ति में सभी तत्वों की जांच की जाती है यदि वे क्रम में हैं। वहाँ अरेन! संभावित क्रमपरिवर्तन; एक संतुलित यादृच्छिक संख्या जनरेटर के साथ, सरणी का लगभग प्रत्येक क्रमपरिवर्तन n में प्राप्त होता है! पुनरावृत्तियाँ कंप्यूटर में सीमित मेमोरी होती है, इसलिए उत्पन्न संख्याएँ चक्रित होती हैं; प्रत्येक क्रमपरिवर्तन तक पहुँचना संभव नहीं हो सकता है। निकृष्ट स्थिति में यह O(∞) समय, एक अनंत लूप की ओर ले जाता है।
डेटा संरचनाएं
| Data structure | Time complexity | Space complexity | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Avg: Indexing | Avg: Search | Avg: Insertion | Avg: Deletion | Worst: Indexing | Worst: Search | Worst: Insertion | Worst: Deletion | Worst | |
| Basic array | O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) |
| Dynamic array | O(1) | O(n) | O(n) | — | O(1) | O(n) | O(n) | — | O(n) |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Singly linked list | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Doubly linked list | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip list | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(n) | O(n) | O(n) | O(n) | O(nlog (n)) |
| Hash table | — | O(1) | O(1) | O(1) | — | O(n) | O(n) | O(n) | O(n) |
| Binary search tree | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| Cartesian tree | — | O(log (n)) | O(log (n)) | O(log (n)) | — | O(n) | O(n) | O(n) | O(n) |
| B-tree | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(n) |
| Red–black tree | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(n) |
| Splay tree | — | O(log (n)) | O(log (n)) | O(log (n)) | — | O(log (n)) | O(log (n)) | O(log (n)) | O(n) |
| AVL tree | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(n) |
| K-d tree | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
- n तत्वों की सूची पर रैखिक खोज। निकृष्ट स्थिति में, खोज को प्रत्येक तत्व पर एक बार अवश्य जाना चाहिए। ऐसा तब होता है जब खोजा जा रहा मान या तो सूची का अंतिम तत्व है, या सूची में नहीं है। हालाँकि, औसतन, यह मानते हुए कि खोजा गया मूल्य सूची में है और प्रत्येक सूची तत्व समान रूप से खोजा गया मूल्य होने की संभावना है, खोज केवल n/2 तत्वों पर जाती है।
यह भी देखें
- सॉर्टिंग एल्गोरिदम - एक ऐसा क्षेत्र जहां विभिन्न एल्गोरिदम के प्रदर्शन विश्लेषण का एक बड़ा हिस्सा है।
- डेटा संरचना खोजें - कोई भी डेटा संरचना जो विशिष्ट वस्तुओं की कुशल पुनर्प्राप्ति की अनुमति देती है
- निकृष्ट स्थिति वाला सर्किट विश्लेषण
- सुचारु विश्लेषण
- अंतराल परिमित तत्व
- बिग ओ अंकन
संदर्भ
- ↑ Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 2 "Getting Started".In Best-case complexity, it gives the lower bound on the running time of the algorithm of any instances of input.
- ↑ Spielman, Daniel; Teng, Shang-Hua (2009), "Smoothed analysis: an attempt to explain the behavior of algorithms in practice" (PDF), Communications of the ACM, ACM, 52 (10): 76-84, doi:10.1145/1562764.1562785, S2CID 7904807
- ↑ "सबसे खराब स्थिति जटिलता" (PDF). Archived (PDF) from the original on 2011-07-21. Retrieved 2008-11-30.
