सर्वोत्तम, निकृष्ट और औसत अवस्था
 | This article needs additional citations for verification. (March 2009) (Learn how and when to remove this template message) |
कंप्यूटर विज्ञान में, किसी दिए गए एल्गोरिदम के सबसे अच्छे, सबसे खराब और औसत मामले यह व्यक्त करते हैं कि संसाधन (कंप्यूटर विज्ञान) का उपयोग क्रमशः कम से कम, अधिकतम और औसतन है। आमतौर पर जिस संसाधन पर विचार किया जा रहा है वह रनिंग टाइम यानी समय जटिलता है, लेकिन यह मेमोरी या कोई अन्य संसाधन भी हो सकता है। सर्वोत्तम स्थिति वह फ़ंक्शन है जो n तत्वों के इनपुट डेटा पर न्यूनतम संख्या में चरण निष्पादित करता है। सबसे खराब स्थिति वह फ़ंक्शन है जो आकार n के इनपुट डेटा पर अधिकतम चरणों को निष्पादित करता है। औसत केस वह फ़ंक्शन है जो n तत्वों के इनपुट डेटा पर औसत संख्या में चरण निष्पादित करता है।
वास्तविक समय कंप्यूटिंग में, सबसे खराब स्थिति में निष्पादन समय अक्सर विशेष चिंता का विषय होता है क्योंकि यह जानना महत्वपूर्ण है कि सबसे खराब स्थिति में कितने समय की आवश्यकता हो सकती है यह गारंटी देने के लिए कि एल्गोरिदम हमेशा समय पर समाप्त होगा।
कलन विधि विश्लेषण में औसत-मामले की जटिलता और सबसे खराब-मामले की जटिलता | सबसे खराब-मामले के प्रदर्शन का सबसे अधिक उपयोग किया जाता है। सर्वोत्तम-मामले का प्रदर्शन कम व्यापक रूप से पाया जाता है, लेकिन इसके उपयोग हैं: उदाहरण के लिए, जहां व्यक्तिगत कार्यों के सर्वोत्तम मामले ज्ञात हैं, उनका उपयोग समग्र सबसे खराब-मामले विश्लेषण की सटीकता में सुधार करने के लिए किया जा सकता है। कंप्यूटर वैज्ञानिक अपेक्षित चलने के समय को निर्धारित करने के लिए संभाव्य विश्लेषण तकनीकों, विशेष रूप से अपेक्षित मूल्य का उपयोग करते हैं।
शब्दों का प्रयोग अन्य संदर्भों में किया जाता है; उदाहरण के लिए किसी महामारी का सबसे खराब और सबसे अच्छा परिणाम, सबसे खराब स्थिति का तापमान जिसके संपर्क में इलेक्ट्रॉनिक सर्किट तत्व आता है, आदि। जहां निर्दिष्ट इंजीनियरिंग सहिष्णुता के घटकों का उपयोग किया जाता है, उपकरणों को सबसे खराब स्थिति के साथ ठीक से काम करने के लिए डिज़ाइन किया जाना चाहिए सहनशीलता और बाहरी परिस्थितियों का संयोजन।
एल्गोरिदम के लिए सर्वश्रेष्ठ प्रदर्शन
सबसे ख़राब प्रदर्शन शब्द का उपयोग कंप्यूटर विज्ञान में इष्टतम परिस्थितियों में एल्गोरिदम के व्यवहार का वर्णन करने के लिए किया जाता है। उदाहरण के लिए, किसी सूची पर सरल रैखिक खोज का सबसे अच्छा मामला तब होता है जब वांछित तत्व सूची का पहला तत्व होता है।
एल्गोरिदम का विकास और चयन शायद ही कभी सर्वोत्तम स्थिति के प्रदर्शन पर आधारित होता है: अधिकांश शैक्षणिक और वाणिज्यिक उद्यम औसत-मामले की जटिलता और सबसे खराब स्थिति के प्रदर्शन में सुधार करने में अधिक रुचि रखते हैं। इनपुट के एक सीमित सेट के लिए हार्ड-कोडिंग समाधानों द्वारा अच्छे सर्वोत्तम मामले में चलने का समय रखने के लिए एल्गोरिदम को मामूली रूप से संशोधित किया जा सकता है, जिससे माप लगभग अर्थहीन हो जाता है।[1]
सबसे खराब स्थिति बनाम परिशोधित बनाम औसत-मामला प्रदर्शन
| This section does not cite any sources. (September 2017) (Learn how and when to remove this template message) |
सबसे खराब स्थिति के प्रदर्शन विश्लेषण और औसत-मामले के प्रदर्शन विश्लेषण में कुछ समानताएं हैं, लेकिन व्यवहार में आमतौर पर विभिन्न उपकरणों और दृष्टिकोणों की आवश्यकता होती है।
यह निर्धारित करना मुश्किल है कि विशिष्ट इनपुट का क्या मतलब है, और अक्सर उस औसत इनपुट में ऐसे गुण होते हैं जो गणितीय रूप से वर्णन करना मुश्किल बनाते हैं (उदाहरण के लिए, एल्गोरिदम पर विचार करें जो पाठ के स्ट्रिंग (कंप्यूटर विज्ञान) पर काम करने के लिए डिज़ाइन किए गए हैं)। इसी तरह, यहां तक कि जब किसी विशेष औसत मामले का एक समझदार विवरण (जो संभवतः केवल एल्गोरिदम के कुछ उपयोगों के लिए लागू होगा) संभव है, तो उनके परिणामस्वरूप समीकरणों का अधिक कठिन विश्लेषण होता है।[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.
