सर्वोत्तम, निकृष्ट और औसत अवस्था: Difference between revisions

From Vigyanwiki
(Created page with "{{Redirect|worst case|the 2010 James Patterson novel|Worst Case|the case|worst-case scenario}} {{Short description|A measure of how efficiently algorithms use resources}} {{Re...")
 
No edit summary
 
(10 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Redirect|worst case|the 2010 James Patterson novel|Worst Case|the case|worst-case scenario}}
{{Redirect|निकृष्ट स्थिति|2010 जेम्स पैटरसन नावेल|निकृष्ट स्थिति|स्थिति|निकृष्ट परिदृश्य}}
{{Short description|A measure of how efficiently algorithms use resources}}
{{Short description|A measure of how efficiently algorithms use resources}}
{{Refimprove|date=March 2009}}
कंप्यूटर विज्ञान में, किसी दिए गए एल्गोरिदम के '''सर्वोत्तम''', '''निकृष्ट''' और '''औसत''' स्थिति क्रमशः यह व्यक्त करते हैं कि संसाधन का उपयोग ''न्यूनतम'', ''अधिकतम'' और ''औसत'' पर क्या है। सामान्यतः, जिस संसाधन पर विचार किया जा रहा है वह रनिंग टाइम है, यानी समय जटिलता, लेकिन मेमोरी या कोई अन्य संसाधन भी हो सकता है। सबसे अच्छा स्थिति वह फ़ंक्शन है जो n घटकों के इनपुट डेटा पर न्यूनतम चरणों को निष्पादित करता है। निकृष्ट स्थिति वह फ़ंक्शन है जो आकार n के इनपुट डेटा पर अधिकतम संख्या में चरण निष्पादित करता है। औसत केस वह फ़ंक्शन है जो n घटकों के इनपुट डेटा पर औसत चरणों की संख्या निष्पादित करता है।
[[कंप्यूटर विज्ञान]] में, किसी दिए गए एल्गोरिदम के सबसे अच्छे, सबसे खराब और औसत मामले यह व्यक्त करते हैं कि [[संसाधन (कंप्यूटर विज्ञान)]] का उपयोग क्रमशः ''कम से कम'', ''अधिकतम'' और ''औसतन'' है। आमतौर पर जिस संसाधन पर विचार किया जा रहा है वह रनिंग टाइम यानी समय जटिलता है, लेकिन यह मेमोरी या कोई अन्य संसाधन भी हो सकता है।
सर्वोत्तम स्थिति वह फ़ंक्शन है जो n तत्वों के इनपुट डेटा पर न्यूनतम संख्या में चरण निष्पादित करता है। सबसे खराब स्थिति वह फ़ंक्शन है जो आकार n के इनपुट डेटा पर अधिकतम चरणों को निष्पादित करता है। औसत केस वह फ़ंक्शन है जो n तत्वों के इनपुट डेटा पर औसत संख्या में चरण निष्पादित करता है।


[[वास्तविक समय कंप्यूटिंग]] में, सबसे खराब स्थिति में निष्पादन समय अक्सर विशेष चिंता का विषय होता है क्योंकि यह जानना महत्वपूर्ण है कि ''सबसे खराब स्थिति में'' कितने समय की आवश्यकता हो सकती है यह गारंटी देने के लिए कि एल्गोरिदम हमेशा समय पर समाप्त होगा।
[[वास्तविक समय कंप्यूटिंग]] में, सबसे निकृष्ट स्थिति में निष्पादन समय प्रायः विशेष चिंता का विषय होता है क्योंकि यह जानना महत्वपूर्ण है कि निकृष्ट स्थिति में यह प्रत्याभूति देने के लिए कितने समय की आवश्यकता हो सकती है कि एल्गोरिदम हमेशा समय पर समाप्त होगा।


[[ कलन विधि ]] विश्लेषण में [[औसत-मामले की जटिलता]] और सबसे खराब-मामले की जटिलता | सबसे खराब-मामले के प्रदर्शन का सबसे अधिक उपयोग किया जाता है। सर्वोत्तम-मामले का प्रदर्शन कम व्यापक रूप से पाया जाता है, लेकिन इसके उपयोग हैं: उदाहरण के लिए, जहां व्यक्तिगत कार्यों के सर्वोत्तम मामले ज्ञात हैं, उनका उपयोग समग्र सबसे खराब-मामले विश्लेषण की सटीकता में सुधार करने के लिए किया जा सकता है। कंप्यूटर वैज्ञानिक अपेक्षित चलने के समय को निर्धारित करने के लिए [[संभाव्य विश्लेषण]] तकनीकों, विशेष रूप से [[अपेक्षित मूल्य]] का उपयोग करते हैं।
एल्गोरिथम विश्लेषण में औसत प्रदर्शन और निकृष्ट स्थिति वाला प्रदर्शन सबसे अधिक उपयोग किया जाता है। सबसे अच्छा प्रदर्शन प्रदर्शन कम व्यापक रूप से पाया जाता है, लेकिन इसके उपयोग भी हैं: उदाहरण के लिए, जहां व्यक्तिगत कार्यों के सर्वोत्तम स्थिति ज्ञात हैं, उनका उपयोग समग्र निकृष्ट स्थिति विश्लेषण की सटीकता में सुधार करने के लिए किया जा सकता है। अपेक्षित चलने का समय निर्धारित करने के लिए कंप्यूटर वैज्ञानिक [[संभाव्य विश्लेषण]] तकनीकों, विशेष रूप से [[अपेक्षित मूल्य]] का उपयोग करते हैं।


शब्दों का प्रयोग अन्य संदर्भों में किया जाता है; उदाहरण के लिए किसी महामारी का सबसे खराब और सबसे अच्छा परिणाम, सबसे खराब स्थिति का तापमान जिसके संपर्क में इलेक्ट्रॉनिक सर्किट तत्व आता है, आदि। जहां निर्दिष्ट [[इंजीनियरिंग सहिष्णुता]] के घटकों का उपयोग किया जाता है, उपकरणों को सबसे खराब स्थिति के साथ ठीक से काम करने के लिए डिज़ाइन किया जाना चाहिए सहनशीलता और बाहरी परिस्थितियों का संयोजन।
इन शब्दों का प्रयोग अन्य सन्दर्भों में किया जाता है; उदाहरण के लिए किसी महामारी का सबसे खराब और सबसे अच्छा परिणाम, निकृष्ट स्थिति वाला तापमान जिसके संपर्क में कोई इलेक्ट्रॉनिक सर्किट घटक आता है, आदि। जहां निर्दिष्ट सहिष्णुता के घटकों का उपयोग किया जाता है, उपकरणों को सहनशीलता और बाहरी परिस्थितियों के निकृष्ट स्थिति संयोजन के साथ ठीक से काम करने के लिए डिज़ाइन किया जाना चाहिए।


== एल्गोरिदम के लिए सर्वश्रेष्ठ प्रदर्शन ==
== एल्गोरिथम के लिए सर्वोत्तम-स्थिति प्रदर्शन ==
{{anchor|BCET}}
''सर्वोत्तम-स्थिति प्रदर्शन'' शब्द का उपयोग कंप्यूटर विज्ञान में इष्टतम परिस्थितियों में एल्गोरिदम के व्यवहार का वर्णन करने के लिए किया जाता है। उदाहरण के लिए, किसी सूची पर सरल रैखिक खोज का सर्वोत्तम स्थिति तब होता है जब वांछित घटक सूची का पहला घटक होता है।


[[सबसे ख़राब प्रदर्शन]] शब्द का उपयोग कंप्यूटर विज्ञान में इष्टतम परिस्थितियों में एल्गोरिदम के व्यवहार का वर्णन करने के लिए किया जाता है। उदाहरण के लिए, किसी सूची पर सरल रैखिक खोज का सबसे अच्छा मामला तब होता है जब वांछित तत्व सूची का पहला तत्व होता है।
एल्गोरिदम का विकास और चयन शायद ही कभी सर्वोत्तम-स्थिति के प्रदर्शन पर आधारित होता है: अधिकांश शैक्षणिक और वाणिज्यिक उद्यम औसत-स्थिति की जटिलता और सबसे खराब-स्थिति के प्रदर्शन में सुधार करने में अधिक रुचि रखते हैं। इनपुट के एक सीमित सेट के लिए हार्ड-कोडिंग समाधानों द्वारा अच्छे सर्वोत्तम-स्थिति में चलने के समय के लिए एल्गोरिदम को भी मामूली रूप से संशोधित किया जा सकता है, जिससे माप लगभग अर्थहीन हो जाता है।<ref>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.</ref>
== निकृष्ट स्थिति बनाम परिशोधित बनाम औसत-स्थिति प्रदर्शन ==
{{see|औसत-स्तिथि जटिलता|परिशोधन विश्लेषण|निकृष्ट स्तिथि जटिलता}}


एल्गोरिदम का विकास और चयन शायद ही कभी सर्वोत्तम स्थिति के प्रदर्शन पर आधारित होता है: अधिकांश शैक्षणिक और वाणिज्यिक उद्यम औसत-मामले की जटिलता और सबसे खराब स्थिति के प्रदर्शन में सुधार करने में अधिक रुचि रखते हैं। इनपुट के एक सीमित सेट के लिए हार्ड-कोडिंग समाधानों द्वारा अच्छे सर्वोत्तम मामले में चलने का समय रखने के लिए एल्गोरिदम को मामूली रूप से संशोधित किया जा सकता है, जिससे माप लगभग अर्थहीन हो जाता है।<ref>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.</ref>
निकृष्ट स्थिति के प्रदर्शन विश्लेषण और औसत-स्तिथि के प्रदर्शन विश्लेषण में कुछ समानताएं हैं, लेकिन व्यवहार में सामान्यतः अलग-अलग टूल और दृष्टिकोण की आवश्यकता होती है।


''विशिष्ट इनपुट'' का क्या मतलब है यह निर्धारित करना कठिन है, और प्रायः उस औसत इनपुट में ऐसे गुण होते हैं जो गणितीय रूप से वर्णन करना कठिन बनाते हैं (उदाहरण के लिए, एल्गोरिदम पर विचार करें जो पाठ के [[स्ट्रिंग (कंप्यूटर विज्ञान)|स्ट्रिंग]] पर काम करने के लिए डिज़ाइन किए गए हैं)। इसी तरह, जब किसी विशेष "औसत स्तिथि" (जो संभवतः केवल एल्गोरिथ्म के कुछ उपयोगों के लिए लागू होगा) का एक समझदार विवरण संभव है, तो उनके परिणामस्वरूप समीकरणों का अधिक कठिन विश्लेषण होता है।<ref>{{Citation | last1 = Spielman | first1 = Daniel | author-link = Daniel Spielman | last2 = Teng | first2 = Shang-Hua | author2-link = Shangua Teng | journal = Communications of the ACM | publisher = ACM | volume = 52 | issue = 10  | year = 2009 | title = Smoothed analysis: an attempt to explain the behavior of algorithms in practice | page = 76-84 | url = http://cs-www.cs.yale.edu/homes/spielman/Research/cacmSmooth.pdf | doi = 10.1145/1562764.1562785| s2cid = 7904807 }}</ref>


== सबसे खराब स्थिति बनाम परिशोधित बनाम औसत-मामला प्रदर्शन ==
निकृष्ट स्थिति का विश्लेषण एक सुरक्षित विश्लेषण देता है (निकृष्ट स्थिति को कभी भी कम करके नहीं आंका जाता है), लेकिन ऐसा विश्लेषण जो अत्यधिक निराशावादी हो सकता है, क्योंकि ऐसा कोई (यथार्थवादी) इनपुट नहीं हो सकता है जो इतने कदम उठाएगा।
{{unreferenced section|date=September 2017}}


{{see|average-case complexity|amortized analysis|worst-case complexity}}
कुछ परिस्थितियों में सुरक्षा की प्रत्याभूति के लिए निराशावादी विश्लेषण का उपयोग करना आवश्यक हो सकता है। हालाँकि, प्रायः एक निराशावादी विश्लेषण बहुत अधिक निराशावादी हो सकता है, इसलिए एक विश्लेषण जो वास्तविक मूल्य के करीब पहुँचता है लेकिन आशावादी हो सकता है (शायद विफलता की कुछ ज्ञात कम संभावना के साथ) अधिक व्यावहारिक दृष्टिकोण हो सकता है। अकादमिक सिद्धांत में निकृष्ट स्थिति और औसत-स्तिथि विश्लेषण के बीच अंतर को पाटने के एक आधुनिक दृष्टिकोण को सहज विश्लेषण कहा जाता है।
 
सबसे खराब स्थिति के प्रदर्शन विश्लेषण और औसत-मामले के प्रदर्शन विश्लेषण में कुछ समानताएं हैं, लेकिन व्यवहार में आमतौर पर विभिन्न उपकरणों और दृष्टिकोणों की आवश्यकता होती है।
 
यह निर्धारित करना मुश्किल है कि विशिष्ट इनपुट का क्या मतलब है, और अक्सर उस औसत इनपुट में ऐसे गुण होते हैं जो गणितीय रूप से वर्णन करना मुश्किल बनाते हैं (उदाहरण के लिए, एल्गोरिदम पर विचार करें जो पाठ के [[स्ट्रिंग (कंप्यूटर विज्ञान)]] पर काम करने के लिए डिज़ाइन किए गए हैं)। इसी तरह, यहां तक ​​कि जब किसी विशेष औसत मामले का एक समझदार विवरण (जो संभवतः केवल एल्गोरिदम के कुछ उपयोगों के लिए लागू होगा) संभव है, तो उनके परिणामस्वरूप समीकरणों का अधिक कठिन विश्लेषण होता है।<ref>{{Citation | last1 = Spielman | first1 = Daniel | author-link = Daniel Spielman | last2 = Teng | first2 = Shang-Hua | author2-link = Shangua Teng | journal = Communications of the ACM | publisher = ACM | volume = 52 | issue = 10  | year = 2009 | title = Smoothed analysis: an attempt to explain the behavior of algorithms in practice | page = 76-84 | url = http://cs-www.cs.yale.edu/homes/spielman/Research/cacmSmooth.pdf | doi = 10.1145/1562764.1562785| s2cid = 7904807 }}</ref>
सबसे खराब स्थिति का विश्लेषण एक सुरक्षित विश्लेषण देता है (सबसे खराब स्थिति को कभी भी कम करके नहीं आंका जाता है), लेकिन ऐसा विश्लेषण जो अत्यधिक निराशावादी हो सकता है, क्योंकि ऐसा कोई (यथार्थवादी) इनपुट नहीं हो सकता है जो इतने सारे कदम उठा सके।
 
कुछ स्थितियों में सुरक्षा की गारंटी के लिए निराशावादी विश्लेषण का उपयोग करना आवश्यक हो सकता है। हालाँकि, अक्सर एक निराशावादी विश्लेषण बहुत निराशावादी हो सकता है, इसलिए एक विश्लेषण जो वास्तविक मूल्य के करीब आता है लेकिन आशावादी हो सकता है (शायद विफलता की कुछ ज्ञात कम संभावना के साथ) अधिक व्यावहारिक दृष्टिकोण हो सकता है। सबसे खराब स्थिति और औसत-मामले विश्लेषण के बीच अंतर को पाटने के लिए अकादमिक सिद्धांत में एक आधुनिक दृष्टिकोण को सुचारू विश्लेषण कहा जाता है।
 
एल्गोरिदम का विश्लेषण करते समय जिसे पूरा होने में अक्सर थोड़ा समय लगता है, लेकिन समय-समय पर बहुत अधिक समय की आवश्यकता होती है, [[परिशोधन विश्लेषण]] का उपयोग [[ऑपरेशन (गणित)]] की (संभवतः अनंत) श्रृंखला पर सबसे खराब स्थिति में चलने वाले समय को निर्धारित करने के लिए किया जा सकता है। यह 'परिशोधन' लागत औसत लागत के बहुत करीब हो सकती है, जबकि अभी भी चलने के समय पर एक गारंटीकृत ऊपरी सीमा प्रदान करती है। तो उदा. [[ऑनलाइन एल्गोरिदम]] अक्सर परिशोधन विश्लेषण पर आधारित होते हैं।
 
सबसे खराब स्थिति का विश्लेषण सबसे खराब स्थिति की जटिलता से संबंधित है।<ref>{{Cite web |url=http://www.fsz.bme.hu/~szirmay/ray6.pdf |title=सबसे खराब स्थिति जटिलता|access-date=2008-11-30 |archive-url=https://web.archive.org/web/20110721103906/http://www.fsz.bme.hu/~szirmay/ray6.pdf |archive-date=2011-07-21 |url-status=live }}</ref>


एल्गोरिदम का विश्लेषण करते समय, जिसे पूरा होने में प्रायः थोड़ा समय लगता है, लेकिन समय-समय पर बहुत अधिक समय की आवश्यकता होती है, संचालन की श्रृंखला (संभवतः अनंत) पर निकृष्ट स्थिति में चलने का समय निर्धारित करने के लिए [[परिशोधन विश्लेषण]] का उपयोग किया जा सकता है। यह परिशोधन लागत औसत लागत के बहुत करीब हो सकती है, जबकि अभी भी चलने के समय पर एक गारंटीकृत ऊपरी सीमा प्रदान की जाती है। तो उदा. [[ऑनलाइन एल्गोरिदम]] प्रायः अमूर्त विश्लेषण पर आधारित होते हैं।


निकृष्ट स्थिति का विश्लेषण निकृष्ट स्थिति की जटिलता से संबंधित है।<ref>{{Cite web |url=http://www.fsz.bme.hu/~szirmay/ray6.pdf |title=सबसे खराब स्थिति जटिलता|access-date=2008-11-30 |archive-url=https://web.archive.org/web/20110721103906/http://www.fsz.bme.hu/~szirmay/ray6.pdf |archive-date=2011-07-21 |url-status=live }}</ref>
== व्यावहारिक परिणाम ==
== व्यावहारिक परिणाम ==
खराब सबसे खराब स्थिति वाले कई एल्गोरिदम का औसत प्रदर्शन अच्छा होता है। जिन समस्याओं को हम हल करना चाहते हैं, उनके लिए यह एक अच्छी बात है: हम आशा कर सकते हैं कि जिन विशेष उदाहरणों की हम परवाह करते हैं वे औसत हैं। [[क्रिप्टोग्राफी]] के लिए, यह बहुत बुरा है: हम चाहते हैं कि क्रिप्टोग्राफ़िक समस्या के विशिष्ट उदाहरण कठिन हों। यहां कुछ विशिष्ट समस्याओं के लिए [[यादृच्छिक स्व-रिड्यूसिबिलिटी]] जैसी विधियों का उपयोग यह दिखाने के लिए किया जा सकता है कि सबसे खराब मामला औसत मामले से अधिक कठिन नहीं है, या, समकक्ष, कि औसत मामला सबसे खराब मामले से आसान नहीं है।
खराब निकृष्ट स्थिति वाले प्रदर्शन वाले कई एल्गोरिदम का औसत-स्थिति प्रदर्शन अच्छा होता है। जिन समस्याओं को हम हल करना चाहते हैं, उनके लिए यह एक अच्छी बात है: हम आशा कर सकते हैं कि जिन विशेष उदाहरणों की हमें परवाह है वे औसत हों। [[क्रिप्टोग्राफी]] के लिए, यह बहुत खराब है: हम चाहते हैं कि क्रिप्टोग्राफ़िक समस्या के विशिष्ट उदाहरण कठिन हों। यहां कुछ विशिष्ट समस्याओं के लिए रैंडम सेल्फ-रिड्यूसिबिलिटी जैसी विधियों का उपयोग यह दिखाने के लिए किया जा सकता है कि सबसे खराब स्तिथि औसत स्तिथि की तुलना में कठिन नहीं है, या, समकक्ष, कि औसत स्तिथि सबसे खराब स्तिथि की तुलना में आसान नहीं है।


दूसरी ओर, हैश टेबल जैसी कुछ डेटा संरचनाओं में सबसे खराब स्थिति वाले व्यवहार बहुत खराब होते हैं, लेकिन पर्याप्त आकार की एक अच्छी तरह से लिखी गई [[हैश तालिका]] सांख्यिकीय रूप से कभी भी सबसे खराब स्थिति नहीं देगी; निष्पादित ऑपरेशनों की औसत संख्या एक घातांकीय क्षय वक्र का अनुसरण करती है, और इसलिए किसी ऑपरेशन का रन टाइम सांख्यिकीय रूप से सीमित होता है।
दूसरी ओर, हैश टेबल जैसी कुछ डेटा संरचनाओं में निकृष्ट स्थिति वाला व्यवहार बहुत खराब होता है, लेकिन पर्याप्त आकार की एक अच्छी तरह से लिखी गई [[हैश तालिका|हैश]] टेबल सांख्यिकीय रूप से कभी भी निकृष्ट स्थिति नहीं देगी; किए गए संचालनों की औसत संख्या एक घातांकीय क्षय वक्र का अनुसरण करती है, और इसलिए किसी संचालन का रन टाइम सांख्यिकीय रूप से सीमित होता है।


== उदाहरण ==
== उदाहरण ==


=== सॉर्टिंग एल्गोरिदम ===
=== सॉर्टिंग एल्गोरिदम ===
{{see also|Sorting algorithm#Comparison of algorithms}}
{{see also|सॉर्टिंग एल्गोरिदम और एल्गोरिदम की तुलना}}
{| class="wikitable"
{| class="wikitable"
|-
|-
! 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(''n''<sup>2</sup>) || O(''n'')
| Quick sort || Array || O(''n'' log(''n''))|| O(''n'' log(''n''))|| O(''n''<sup>2</sup>) || O(''n'')
Line 65: Line 56:
| Bogo sort || Array || O(''n'') || O(''n'' ''n''!) || O(∞) || O(1)
| Bogo sort || Array || O(''n'') || O(''n'' ''n''!) || O(∞) || O(1)
|}
|}
[[File:Comparison computational complexity.svg|thumb|आमतौर पर एल्गोरिदम के विश्लेषण में उपयोग किए जाने वाले फ़ंक्शन के ग्राफ़, प्रत्येक फ़ंक्शन के लिए ऑपरेशन एन बनाम इनपुट आकार एन की संख्या दिखाते हैं]]* [[सम्मिलन सॉर्ट]] को n तत्वों की सूची पर लागू किया जाता है, जिसे सभी अलग-अलग और प्रारंभ में यादृच्छिक क्रम में माना जाता है। औसतन, सूची ए में आधे तत्व<sub>1</sub> ... ए<sub>''j''</sub> तत्व A से कम हैं<sub>''j''+1</sub>, और आधे बड़े हैं। इसलिए, एल्गोरिदम (j + 1) की तुलना करता है<sup>वें</sup>तत्व को पहले से ही क्रमबद्ध उप-सूची के आधे के साथ औसतन डाला जाना है, इसलिए टी<sub>''j''</sub> = जे/2. परिणामी औसत-केस रनिंग टाइम पर काम करने से सबसे खराब स्थिति वाले रनिंग टाइम की तरह, इनपुट आकार का एक द्विघात फ़ंक्शन प्राप्त होता है।
[[File:Comparison computational complexity.svg|thumb|सामान्यतः एल्गोरिदम के विश्लेषण में उपयोग किए जाने वाले फ़ंक्शन के ग्राफ़, प्रत्येक फ़ंक्शन के लिए संचालन एन बनाम इनपुट आकार एन की संख्या दिखाते हैं]]
* [[जल्दी से सुलझाएं]] को n तत्वों की सूची पर लागू किया गया, फिर से सभी को अलग-अलग और प्रारंभ में यादृच्छिक क्रम में माना गया। इस लोकप्रिय [[छँटाई एल्गोरिथ्म]] का औसत-केस प्रदर्शन O(n log(n)) है, जो इसे व्यवहार में बहुत तेज़ एल्गोरिदम बनाने में योगदान देता है। लेकिन सबसे खराब स्थिति वाले इनपुट को देखते हुए, इसका प्रदर्शन घटकर O(n) हो जाता है<sup>2</sup>). साथ ही, जब सबसे छोटी पहली नीति के साथ कार्यान्वित किया जाता है, तो सबसे खराब स्थिति वाली स्थान जटिलता O(log(n)) से बंधी होती है।
 
* हीपसॉर्ट में O(n) समय होता है जब सभी तत्व समान होते हैं। हीपिफाई में O(n) समय लगता है और फिर ढेर से तत्वों को हटाने में प्रत्येक n तत्व के लिए O(1) समय लगता है। यदि सभी तत्व अलग-अलग होने चाहिए तो रन टाइम बढ़कर O(nlog(n)) हो जाता है।
* '''प्रविष्टि क्रम''' को n घटकों की सूची पर लागू किया जाता है, जिसे सभी अलग-अलग माना जाता है और प्रारंभ में यादृच्छिक क्रम में होता है। औसतन, किसी सूची ''A''<sub>1</sub> ... ''A<sub>j</sub>'' में आधे घटक घटक ''A<sub>j</sub>''<sub>+1</sub> से छोटे हैं, और आधे अधिक हैं। इसलिए, एल्गोरिदम औसतन डाले जाने वाले (''j'' + 1)वें घटक की तुलना पहले से ही क्रमबद्ध उप-सूची के आधे से करता है, इसलिए ''t<sub>j</sub>'' = ''j''/2। परिणामी औसत-केस रनिंग टाइम पर काम करने से निकृष्ट स्थिति वाले रनिंग टाइम की तरह, इनपुट आकार का एक द्विघात फ़ंक्शन प्राप्त होता है।
* [[बोगोसोर्ट]] में O(n) समय होता है जब तत्वों को पहले पुनरावृत्ति पर क्रमबद्ध किया जाता है। प्रत्येक पुनरावृत्ति में सभी तत्वों की जांच की जाती है यदि वे क्रम में हैं। वहाँ अरेन! संभावित क्रमपरिवर्तन; एक संतुलित यादृच्छिक संख्या जनरेटर के साथ, सरणी का लगभग प्रत्येक क्रमपरिवर्तन n में प्राप्त होता है! पुनरावृत्तियाँ कंप्यूटर में सीमित मेमोरी होती है, इसलिए उत्पन्न संख्याएँ चक्रित होती हैं; प्रत्येक क्रमपरिवर्तन तक पहुँचना संभव नहीं हो सकता है। सबसे खराब स्थिति में यह O(∞) समय, एक अनंत लूप की ओर ले जाता है।
* '''शीघ्र क्रम''' को ''n'' घटकों की एक सूची पर लागू किया गया, फिर से सभी को अलग-अलग माना गया और प्रारम्भ में यादृच्छिक क्रम में। इस लोकप्रिय सॉर्टिंग एल्गोरिदम का औसत-केस प्रदर्शन O(''n'' log(''n'')) है, जो इसे व्यवहार में बहुत तेज़ एल्गोरिदम बनाने में योगदान देता है। लेकिन निकृष्ट स्थिति में इनपुट दिए जाने पर, इसका प्रदर्शन घटकर O(''n''<sup>2</sup>) हो जाता है। इसके अलावा, जब "सबसे पहले" नीति के साथ कार्यान्वित किया जाता है, तो निकृष्ट स्थिति वाली स्थान जटिलता O(log(''n'')) से बंधी होती है।
* जब सभी घटक समान होते हैं तो हीप्सॉर्ट का O(n) समय होता है। हीपिफ़ाइ में O(n) समय लगता है और फिर स्टैक से घटकों को हटाने में प्रत्येक n घटक के लिए O(1) समय लगता है। यदि सभी घटक अलग-अलग होने चाहिए तो रन टाइम O(nlog(n)) तक बढ़ जाता है।
* जब घटकों को पहले पुनरावृत्ति पर क्रमबद्ध किया जाता है तो [[बोगोसोर्ट|बोगोसॉर्ट]] के पास O(n) समय होता है। प्रत्येक पुनरावृत्ति में सभी घटकों की जाँच क्रम में की जाती है। वहाँ अरेन! संभावित क्रमचय; एक संतुलित यादृच्छिक संख्या जनरेटर के साथ, सरणी के लगभग प्रत्येक क्रमपरिवर्तन n में उत्पन्न होता है! पुनरावृत्तियाँ कंप्यूटर की मेमोरी सीमित होती है, इसलिए उत्पन्न संख्याएँ चक्रित होती हैं; प्रत्येक क्रमपरिवर्तन तक पहुँचना संभव नहीं हो सकता है। निकृष्ट स्थिति में यह O(∞) समय, एक अनंत लूप की ओर ले जाता है।


=== डेटा संरचनाएं ===
=== डेटा संरचनाएं ===
{{see also|Search data structure#Asymptotic worst-case analysis}}
{{see also|खोज डेटा संरचना और स्पर्शोन्मुख निकृष्ट स्थिति विश्लेषण}}
{| class="wikitable"
{| class="wikitable"
! rowspan=2 |Data structure
! rowspan=2 |डेटा संरचना
! colspan=8 |Time complexity
! colspan=8 |समय जटिलता
!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'')
| Basic [[array]] || O(1) || O(''n'') ||O(''n'') ||O(''n'') || O(1) || O(''n'') || O(''n'') || O(''n'') || O(''n'')
Line 109: Line 102:
| [[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'')
| [[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 तत्वों पर जाती है।
* ''n'' घटकों की सूची पर रेखीय खोज। निकृष्ट स्थिति में, खोज को प्रत्येक घटक पर एक बार जाना होगा। ऐसा तब होता है जब खोजा जा रहा मान या तो सूची का अंतिम घटक होता है, या सूची में नहीं होता है। हालाँकि, औसतन, यह मानते हुए कि खोजा गया मान सूची में है और प्रत्येक सूची घटक के लिए खोजा गया मान होने की समान रूप से संभावना है, खोज केवल ''n/2'' घटकों पर जाती है।


== यह भी देखें ==
== यह भी देखें ==
* सॉर्टिंग एल्गोरिदम - एक ऐसा क्षेत्र जहां विभिन्न एल्गोरिदम के प्रदर्शन विश्लेषण का एक बड़ा हिस्सा है।
 
* [[डेटा संरचना खोजें]] - कोई भी डेटा संरचना जो विशिष्ट वस्तुओं की कुशल पुनर्प्राप्ति की अनुमति देती है
* सॉर्टिंग एल्गोरिदम - एक ऐसा क्षेत्र जहां विभिन्न एल्गोरिदम का प्रदर्शन विश्लेषण बहुत अधिक है।
* [[सबसे खराब स्थिति वाला सर्किट विश्लेषण]]
* डेटा संरचना खोजें - कोई भी डेटा संरचना जो विशिष्ट वस्तुओं की कुशल पुनर्प्राप्ति की अनुमति देती है।
* निकृष्ट सर्किट विश्लेषण
* सुचारु विश्लेषण
* सुचारु विश्लेषण
*[[अंतराल परिमित तत्व]]
* [[अंतराल परिमित तत्व|अंतराल परिमित घटक]]
* [[ बिग ओ अंकन ]]
* बिग ओ नोटेशन


== संदर्भ ==
== संदर्भ ==
{{Reflist}}
{{Reflist}}


{{DEFAULTSORT:Best, Worst And Average Case}}[[Category: कम्प्यूटेशनल जटिलता सिद्धांत]] [[Category: एल्गोरिदम का विश्लेषण]]
{{DEFAULTSORT:Best, Worst And Average Case}}
 
 


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page|Best, Worst And Average Case]]
[[Category:Created On 07/07/2023]]
[[Category:Created On 07/07/2023|Best, Worst And Average Case]]
[[Category:Lua-based templates|Best, Worst And Average Case]]
[[Category:Machine Translated Page|Best, Worst And Average Case]]
[[Category:Missing redirects|Best, Worst And Average Case]]
[[Category:Pages with script errors|Best, Worst And Average Case]]
[[Category:Templates Vigyan Ready|Best, Worst And Average Case]]
[[Category:Templates that add a tracking category|Best, Worst And Average Case]]
[[Category:Templates that generate short descriptions|Best, Worst And Average Case]]
[[Category:Templates using TemplateData|Best, Worst And Average Case]]
[[Category:एल्गोरिदम का विश्लेषण|Best, Worst And Average Case]]
[[Category:कम्प्यूटेशनल जटिलता सिद्धांत|Best, Worst And Average Case]]

Latest revision as of 09:35, 27 July 2023

"निकृष्ट स्थिति" redirects here. For 2010 जेम्स पैटरसन नावेल, see निकृष्ट स्थिति. For स्थिति, see निकृष्ट परिदृश्य.

कंप्यूटर विज्ञान में, किसी दिए गए एल्गोरिदम के सर्वोत्तम, निकृष्ट और औसत स्थिति क्रमशः यह व्यक्त करते हैं कि संसाधन का उपयोग न्यूनतम, अधिकतम और औसत पर क्या है। सामान्यतः, जिस संसाधन पर विचार किया जा रहा है वह रनिंग टाइम है, यानी समय जटिलता, लेकिन मेमोरी या कोई अन्य संसाधन भी हो सकता है। सबसे अच्छा स्थिति वह फ़ंक्शन है जो n घटकों के इनपुट डेटा पर न्यूनतम चरणों को निष्पादित करता है। निकृष्ट स्थिति वह फ़ंक्शन है जो आकार n के इनपुट डेटा पर अधिकतम संख्या में चरण निष्पादित करता है। औसत केस वह फ़ंक्शन है जो n घटकों के इनपुट डेटा पर औसत चरणों की संख्या निष्पादित करता है।

वास्तविक समय कंप्यूटिंग में, सबसे निकृष्ट स्थिति में निष्पादन समय प्रायः विशेष चिंता का विषय होता है क्योंकि यह जानना महत्वपूर्ण है कि निकृष्ट स्थिति में यह प्रत्याभूति देने के लिए कितने समय की आवश्यकता हो सकती है कि एल्गोरिदम हमेशा समय पर समाप्त होगा।

एल्गोरिथम विश्लेषण में औसत प्रदर्शन और निकृष्ट स्थिति वाला प्रदर्शन सबसे अधिक उपयोग किया जाता है। सबसे अच्छा प्रदर्शन प्रदर्शन कम व्यापक रूप से पाया जाता है, लेकिन इसके उपयोग भी हैं: उदाहरण के लिए, जहां व्यक्तिगत कार्यों के सर्वोत्तम स्थिति ज्ञात हैं, उनका उपयोग समग्र निकृष्ट स्थिति विश्लेषण की सटीकता में सुधार करने के लिए किया जा सकता है। अपेक्षित चलने का समय निर्धारित करने के लिए कंप्यूटर वैज्ञानिक संभाव्य विश्लेषण तकनीकों, विशेष रूप से अपेक्षित मूल्य का उपयोग करते हैं।

इन शब्दों का प्रयोग अन्य सन्दर्भों में किया जाता है; उदाहरण के लिए किसी महामारी का सबसे खराब और सबसे अच्छा परिणाम, निकृष्ट स्थिति वाला तापमान जिसके संपर्क में कोई इलेक्ट्रॉनिक सर्किट घटक आता है, आदि। जहां निर्दिष्ट सहिष्णुता के घटकों का उपयोग किया जाता है, उपकरणों को सहनशीलता और बाहरी परिस्थितियों के निकृष्ट स्थिति संयोजन के साथ ठीक से काम करने के लिए डिज़ाइन किया जाना चाहिए।

एल्गोरिथम के लिए सर्वोत्तम-स्थिति प्रदर्शन

सर्वोत्तम-स्थिति प्रदर्शन शब्द का उपयोग कंप्यूटर विज्ञान में इष्टतम परिस्थितियों में एल्गोरिदम के व्यवहार का वर्णन करने के लिए किया जाता है। उदाहरण के लिए, किसी सूची पर सरल रैखिक खोज का सर्वोत्तम स्थिति तब होता है जब वांछित घटक सूची का पहला घटक होता है।

एल्गोरिदम का विकास और चयन शायद ही कभी सर्वोत्तम-स्थिति के प्रदर्शन पर आधारित होता है: अधिकांश शैक्षणिक और वाणिज्यिक उद्यम औसत-स्थिति की जटिलता और सबसे खराब-स्थिति के प्रदर्शन में सुधार करने में अधिक रुचि रखते हैं। इनपुट के एक सीमित सेट के लिए हार्ड-कोडिंग समाधानों द्वारा अच्छे सर्वोत्तम-स्थिति में चलने के समय के लिए एल्गोरिदम को भी मामूली रूप से संशोधित किया जा सकता है, जिससे माप लगभग अर्थहीन हो जाता है।[1]

निकृष्ट स्थिति बनाम परिशोधित बनाम औसत-स्थिति प्रदर्शन

Further information: औसत-स्तिथि जटिलता, परिशोधन विश्लेषण, and निकृष्ट स्तिथि जटिलता

निकृष्ट स्थिति के प्रदर्शन विश्लेषण और औसत-स्तिथि के प्रदर्शन विश्लेषण में कुछ समानताएं हैं, लेकिन व्यवहार में सामान्यतः अलग-अलग टूल और दृष्टिकोण की आवश्यकता होती है।

विशिष्ट इनपुट का क्या मतलब है यह निर्धारित करना कठिन है, और प्रायः उस औसत इनपुट में ऐसे गुण होते हैं जो गणितीय रूप से वर्णन करना कठिन बनाते हैं (उदाहरण के लिए, एल्गोरिदम पर विचार करें जो पाठ के स्ट्रिंग पर काम करने के लिए डिज़ाइन किए गए हैं)। इसी तरह, जब किसी विशेष "औसत स्तिथि" (जो संभवतः केवल एल्गोरिथ्म के कुछ उपयोगों के लिए लागू होगा) का एक समझदार विवरण संभव है, तो उनके परिणामस्वरूप समीकरणों का अधिक कठिन विश्लेषण होता है।[2]

निकृष्ट स्थिति का विश्लेषण एक सुरक्षित विश्लेषण देता है (निकृष्ट स्थिति को कभी भी कम करके नहीं आंका जाता है), लेकिन ऐसा विश्लेषण जो अत्यधिक निराशावादी हो सकता है, क्योंकि ऐसा कोई (यथार्थवादी) इनपुट नहीं हो सकता है जो इतने कदम उठाएगा।

कुछ परिस्थितियों में सुरक्षा की प्रत्याभूति के लिए निराशावादी विश्लेषण का उपयोग करना आवश्यक हो सकता है। हालाँकि, प्रायः एक निराशावादी विश्लेषण बहुत अधिक निराशावादी हो सकता है, इसलिए एक विश्लेषण जो वास्तविक मूल्य के करीब पहुँचता है लेकिन आशावादी हो सकता है (शायद विफलता की कुछ ज्ञात कम संभावना के साथ) अधिक व्यावहारिक दृष्टिकोण हो सकता है। अकादमिक सिद्धांत में निकृष्ट स्थिति और औसत-स्तिथि विश्लेषण के बीच अंतर को पाटने के एक आधुनिक दृष्टिकोण को सहज विश्लेषण कहा जाता है।

एल्गोरिदम का विश्लेषण करते समय, जिसे पूरा होने में प्रायः थोड़ा समय लगता है, लेकिन समय-समय पर बहुत अधिक समय की आवश्यकता होती है, संचालन की श्रृंखला (संभवतः अनंत) पर निकृष्ट स्थिति में चलने का समय निर्धारित करने के लिए परिशोधन विश्लेषण का उपयोग किया जा सकता है। यह परिशोधन लागत औसत लागत के बहुत करीब हो सकती है, जबकि अभी भी चलने के समय पर एक गारंटीकृत ऊपरी सीमा प्रदान की जाती है। तो उदा. ऑनलाइन एल्गोरिदम प्रायः अमूर्त विश्लेषण पर आधारित होते हैं।

निकृष्ट स्थिति का विश्लेषण निकृष्ट स्थिति की जटिलता से संबंधित है।[3]

व्यावहारिक परिणाम

खराब निकृष्ट स्थिति वाले प्रदर्शन वाले कई एल्गोरिदम का औसत-स्थिति प्रदर्शन अच्छा होता है। जिन समस्याओं को हम हल करना चाहते हैं, उनके लिए यह एक अच्छी बात है: हम आशा कर सकते हैं कि जिन विशेष उदाहरणों की हमें परवाह है वे औसत हों। क्रिप्टोग्राफी के लिए, यह बहुत खराब है: हम चाहते हैं कि क्रिप्टोग्राफ़िक समस्या के विशिष्ट उदाहरण कठिन हों। यहां कुछ विशिष्ट समस्याओं के लिए रैंडम सेल्फ-रिड्यूसिबिलिटी जैसी विधियों का उपयोग यह दिखाने के लिए किया जा सकता है कि सबसे खराब स्तिथि औसत स्तिथि की तुलना में कठिन नहीं है, या, समकक्ष, कि औसत स्तिथि सबसे खराब स्तिथि की तुलना में आसान नहीं है।

दूसरी ओर, हैश टेबल जैसी कुछ डेटा संरचनाओं में निकृष्ट स्थिति वाला व्यवहार बहुत खराब होता है, लेकिन पर्याप्त आकार की एक अच्छी तरह से लिखी गई हैश टेबल सांख्यिकीय रूप से कभी भी निकृष्ट स्थिति नहीं देगी; किए गए संचालनों की औसत संख्या एक घातांकीय क्षय वक्र का अनुसरण करती है, और इसलिए किसी संचालन का रन टाइम सांख्यिकीय रूप से सीमित होता है।

उदाहरण

सॉर्टिंग एल्गोरिदम

See also: सॉर्टिंग एल्गोरिदम और एल्गोरिदम की तुलना
एल्गोरिदम डेटा संरचना समय जटिलता: सर्वोत्तम समय जटिलता:औसत समय जटिलता: निकृष्ट स्पेस जटिलता: निकृष्ट
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(∞) समय, एक अनंत लूप की ओर ले जाता है।

डेटा संरचनाएं

See also: खोज डेटा संरचना और स्पर्शोन्मुख निकृष्ट स्थिति विश्लेषण
डेटा संरचना समय जटिलता समष्टि जटिलता
औसत: अनुक्रमण औसत: खोजें औसत: प्रविष्टि औसत: विलोपन निकृष्ट: अनुक्रमणिका निकृष्ट: खोजें निकृष्ट: प्रविष्टि निकृष्ट: विलोपन निकृष्ट
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 घटकों पर जाती है।

यह भी देखें

  • सॉर्टिंग एल्गोरिदम - एक ऐसा क्षेत्र जहां विभिन्न एल्गोरिदम का प्रदर्शन विश्लेषण बहुत अधिक है।
  • डेटा संरचना खोजें - कोई भी डेटा संरचना जो विशिष्ट वस्तुओं की कुशल पुनर्प्राप्ति की अनुमति देती है।
  • निकृष्ट सर्किट विश्लेषण
  • सुचारु विश्लेषण
  • अंतराल परिमित घटक
  • बिग ओ नोटेशन

संदर्भ

  1. ↑ 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.
  2. ↑ 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
  3. ↑ "सबसे खराब स्थिति जटिलता" (PDF). Archived (PDF) from the original on 2011-07-21. Retrieved 2008-11-30.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सर्वोत्तम,_निकृष्ट_और_औसत_अवस्था&oldid=226521’