सर्वोत्तम, निकृष्ट और औसत अवस्था
कंप्यूटर विज्ञान में, किसी दिए गए एल्गोरिदम के सर्वोत्तम, निकृष्ट और औसत स्थिति क्रमशः यह व्यक्त करते हैं कि संसाधन का उपयोग न्यूनतम, अधिकतम और औसत पर क्या है। सामान्यतः, जिस संसाधन पर विचार किया जा रहा है वह रनिंग टाइम है, यानी समय जटिलता, लेकिन मेमोरी या कोई अन्य संसाधन भी हो सकता है। सबसे अच्छा स्थिति वह फ़ंक्शन है जो n घटकों के इनपुट डेटा पर न्यूनतम चरणों को निष्पादित करता है। निकृष्ट स्थिति वह फ़ंक्शन है जो आकार n के इनपुट डेटा पर अधिकतम संख्या में चरण निष्पादित करता है। औसत केस वह फ़ंक्शन है जो n घटकों के इनपुट डेटा पर औसत चरणों की संख्या निष्पादित करता है।
वास्तविक समय कंप्यूटिंग में, सबसे निकृष्ट स्थिति में निष्पादन समय प्रायः विशेष चिंता का विषय होता है क्योंकि यह जानना महत्वपूर्ण है कि निकृष्ट स्थिति में यह प्रत्याभूति देने के लिए कितने समय की आवश्यकता हो सकती है कि एल्गोरिदम हमेशा समय पर समाप्त होगा।
एल्गोरिथम विश्लेषण में औसत प्रदर्शन और निकृष्ट स्थिति वाला प्रदर्शन सबसे अधिक उपयोग किया जाता है। सबसे अच्छा प्रदर्शन प्रदर्शन कम व्यापक रूप से पाया जाता है, लेकिन इसके उपयोग भी हैं: उदाहरण के लिए, जहां व्यक्तिगत कार्यों के सर्वोत्तम स्थिति ज्ञात हैं, उनका उपयोग समग्र निकृष्ट स्थिति विश्लेषण की सटीकता में सुधार करने के लिए किया जा सकता है। अपेक्षित चलने का समय निर्धारित करने के लिए कंप्यूटर वैज्ञानिक संभाव्य विश्लेषण तकनीकों, विशेष रूप से अपेक्षित मूल्य का उपयोग करते हैं।
इन शब्दों का प्रयोग अन्य सन्दर्भों में किया जाता है; उदाहरण के लिए किसी महामारी का सबसे खराब और सबसे अच्छा परिणाम, निकृष्ट स्थिति वाला तापमान जिसके संपर्क में कोई इलेक्ट्रॉनिक सर्किट घटक आता है, आदि। जहां निर्दिष्ट सहिष्णुता के घटकों का उपयोग किया जाता है, उपकरणों को सहनशीलता और बाहरी परिस्थितियों के निकृष्ट स्थिति संयोजन के साथ ठीक से काम करने के लिए डिज़ाइन किया जाना चाहिए।
एल्गोरिथम के लिए सर्वोत्तम-स्थिति प्रदर्शन
सर्वोत्तम-स्थिति प्रदर्शन शब्द का उपयोग कंप्यूटर विज्ञान में इष्टतम परिस्थितियों में एल्गोरिदम के व्यवहार का वर्णन करने के लिए किया जाता है। उदाहरण के लिए, किसी सूची पर सरल रैखिक खोज का सर्वोत्तम स्थिति तब होता है जब वांछित घटक सूची का पहला घटक होता है।
एल्गोरिदम का विकास और चयन शायद ही कभी सर्वोत्तम-स्थिति के प्रदर्शन पर आधारित होता है: अधिकांश शैक्षणिक और वाणिज्यिक उद्यम औसत-स्थिति की जटिलता और सबसे खराब-स्थिति के प्रदर्शन में सुधार करने में अधिक रुचि रखते हैं। इनपुट के एक सीमित सेट के लिए हार्ड-कोडिंग समाधानों द्वारा अच्छे सर्वोत्तम-स्थिति में चलने के समय के लिए एल्गोरिदम को भी मामूली रूप से संशोधित किया जा सकता है, जिससे माप लगभग अर्थहीन हो जाता है।[1]
निकृष्ट स्थिति बनाम परिशोधित बनाम औसत-स्थिति प्रदर्शन
निकृष्ट स्थिति के प्रदर्शन विश्लेषण और औसत-स्तिथि के प्रदर्शन विश्लेषण में कुछ समानताएं हैं, लेकिन व्यवहार में सामान्यतः अलग-अलग टूल और दृष्टिकोण की आवश्यकता होती है।
विशिष्ट इनपुट का क्या मतलब है यह निर्धारित करना कठिन है, और प्रायः उस औसत इनपुट में ऐसे गुण होते हैं जो गणितीय रूप से वर्णन करना कठिन बनाते हैं (उदाहरण के लिए, एल्गोरिदम पर विचार करें जो पाठ के स्ट्रिंग पर काम करने के लिए डिज़ाइन किए गए हैं)। इसी तरह, जब किसी विशेष "औसत स्तिथि" (जो संभवतः केवल एल्गोरिथ्म के कुछ उपयोगों के लिए लागू होगा) का एक समझदार विवरण संभव है, तो उनके परिणामस्वरूप समीकरणों का अधिक कठिन विश्लेषण होता है।[2]
निकृष्ट स्थिति का विश्लेषण एक सुरक्षित विश्लेषण देता है (निकृष्ट स्थिति को कभी भी कम करके नहीं आंका जाता है), लेकिन ऐसा विश्लेषण जो अत्यधिक निराशावादी हो सकता है, क्योंकि ऐसा कोई (यथार्थवादी) इनपुट नहीं हो सकता है जो इतने कदम उठाएगा।
कुछ परिस्थितियों में सुरक्षा की प्रत्याभूति के लिए निराशावादी विश्लेषण का उपयोग करना आवश्यक हो सकता है। हालाँकि, प्रायः एक निराशावादी विश्लेषण बहुत अधिक निराशावादी हो सकता है, इसलिए एक विश्लेषण जो वास्तविक मूल्य के करीब पहुँचता है लेकिन आशावादी हो सकता है (शायद विफलता की कुछ ज्ञात कम संभावना के साथ) अधिक व्यावहारिक दृष्टिकोण हो सकता है। अकादमिक सिद्धांत में निकृष्ट स्थिति और औसत-स्तिथि विश्लेषण के बीच अंतर को पाटने के एक आधुनिक दृष्टिकोण को सहज विश्लेषण कहा जाता है।
एल्गोरिदम का विश्लेषण करते समय, जिसे पूरा होने में प्रायः थोड़ा समय लगता है, लेकिन समय-समय पर बहुत अधिक समय की आवश्यकता होती है, संचालन की श्रृंखला (संभवतः अनंत) पर निकृष्ट स्थिति में चलने का समय निर्धारित करने के लिए परिशोधन विश्लेषण का उपयोग किया जा सकता है। यह परिशोधन लागत औसत लागत के बहुत करीब हो सकती है, जबकि अभी भी चलने के समय पर एक गारंटीकृत ऊपरी सीमा प्रदान की जाती है। तो उदा. ऑनलाइन एल्गोरिदम प्रायः अमूर्त विश्लेषण पर आधारित होते हैं।
निकृष्ट स्थिति का विश्लेषण निकृष्ट स्थिति की जटिलता से संबंधित है।[3]
व्यावहारिक परिणाम
खराब निकृष्ट स्थिति वाले प्रदर्शन वाले कई एल्गोरिदम का औसत-स्थिति प्रदर्शन अच्छा होता है। जिन समस्याओं को हम हल करना चाहते हैं, उनके लिए यह एक अच्छी बात है: हम आशा कर सकते हैं कि जिन विशेष उदाहरणों की हमें परवाह है वे औसत हों। क्रिप्टोग्राफी के लिए, यह बहुत खराब है: हम चाहते हैं कि क्रिप्टोग्राफ़िक समस्या के विशिष्ट उदाहरण कठिन हों। यहां कुछ विशिष्ट समस्याओं के लिए रैंडम सेल्फ-रिड्यूसिबिलिटी जैसी विधियों का उपयोग यह दिखाने के लिए किया जा सकता है कि सबसे खराब स्तिथि औसत स्तिथि की तुलना में कठिन नहीं है, या, समकक्ष, कि औसत स्तिथि सबसे खराब स्तिथि की तुलना में आसान नहीं है।
दूसरी ओर, हैश टेबल जैसी कुछ डेटा संरचनाओं में निकृष्ट स्थिति वाला व्यवहार बहुत खराब होता है, लेकिन पर्याप्त आकार की एक अच्छी तरह से लिखी गई हैश टेबल सांख्यिकीय रूप से कभी भी निकृष्ट स्थिति नहीं देगी; किए गए संचालनों की औसत संख्या एक घातांकीय क्षय वक्र का अनुसरण करती है, और इसलिए किसी संचालन का रन टाइम सांख्यिकीय रूप से सीमित होता है।
उदाहरण
सॉर्टिंग एल्गोरिदम
| एल्गोरिदम | डेटा संरचना | समय जटिलता: सर्वोत्तम | समय जटिलता:औसत | समय जटिलता: निकृष्ट | स्पेस जटिलता: निकृष्ट |
|---|---|---|---|---|---|
| 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 घटकों की सूची पर लागू किया जाता है, जिसे सभी अलग-अलग माना जाता है और प्रारंभ में यादृच्छिक क्रम में होता है। औसतन, किसी सूची A1 ... Aj में आधे घटक घटक Aj+1 से छोटे हैं, और आधे अधिक हैं। इसलिए, एल्गोरिदम औसतन डाले जाने वाले (j + 1)वें घटक की तुलना पहले से ही क्रमबद्ध उप-सूची के आधे से करता है, इसलिए tj = j/2। परिणामी औसत-केस रनिंग टाइम पर काम करने से निकृष्ट स्थिति वाले रनिंग टाइम की तरह, इनपुट आकार का एक द्विघात फ़ंक्शन प्राप्त होता है।
- शीघ्र क्रम को n घटकों की एक सूची पर लागू किया गया, फिर से सभी को अलग-अलग माना गया और प्रारम्भ में यादृच्छिक क्रम में। इस लोकप्रिय सॉर्टिंग एल्गोरिदम का औसत-केस प्रदर्शन O(n log(n)) है, जो इसे व्यवहार में बहुत तेज़ एल्गोरिदम बनाने में योगदान देता है। लेकिन निकृष्ट स्थिति में इनपुट दिए जाने पर, इसका प्रदर्शन घटकर O(n2) हो जाता है। इसके अलावा, जब "सबसे पहले" नीति के साथ कार्यान्वित किया जाता है, तो निकृष्ट स्थिति वाली स्थान जटिलता O(log(n)) से बंधी होती है।
- जब सभी घटक समान होते हैं तो हीप्सॉर्ट का O(n) समय होता है। हीपिफ़ाइ में O(n) समय लगता है और फिर स्टैक से घटकों को हटाने में प्रत्येक n घटक के लिए O(1) समय लगता है। यदि सभी घटक अलग-अलग होने चाहिए तो रन टाइम O(nlog(n)) तक बढ़ जाता है।
- जब घटकों को पहले पुनरावृत्ति पर क्रमबद्ध किया जाता है तो बोगोसॉर्ट के पास O(n) समय होता है। प्रत्येक पुनरावृत्ति में सभी घटकों की जाँच क्रम में की जाती है। वहाँ अरेन! संभावित क्रमचय; एक संतुलित यादृच्छिक संख्या जनरेटर के साथ, सरणी के लगभग प्रत्येक क्रमपरिवर्तन n में उत्पन्न होता है! पुनरावृत्तियाँ कंप्यूटर की मेमोरी सीमित होती है, इसलिए उत्पन्न संख्याएँ चक्रित होती हैं; प्रत्येक क्रमपरिवर्तन तक पहुँचना संभव नहीं हो सकता है। निकृष्ट स्थिति में यह O(∞) समय, एक अनंत लूप की ओर ले जाता है।
डेटा संरचनाएं
| डेटा संरचना | समय जटिलता | समष्टि जटिलता | |||||||
|---|---|---|---|---|---|---|---|---|---|
| औसत: अनुक्रमण | औसत: खोजें | औसत: प्रविष्टि | औसत: विलोपन | निकृष्ट: अनुक्रमणिका | निकृष्ट: खोजें | निकृष्ट: प्रविष्टि | निकृष्ट: विलोपन | निकृष्ट | |
| 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.
