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

From Vigyanwiki
No edit summary
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Redirect|निकृष्ट स्थिति|2010 जेम्स पैटरसन नावेल|निकृष्ट स्थिति|स्थिति|निकृष्ट परिदृश्य}}
{{Redirect|निकृष्ट स्थिति|2010 जेम्स पैटरसन नावेल|निकृष्ट स्थिति|स्थिति|निकृष्ट परिदृश्य}}
{{Short description|A measure of how efficiently algorithms use resources}}
{{Short description|A measure of how efficiently algorithms use resources}}
कंप्यूटर विज्ञान में, किसी दिए गए एल्गोरिदम के '''सर्वोत्तम''', '''निकृष्ट''' और '''औसत''' स्थिति क्रमशः यह व्यक्त करते हैं कि संसाधन का उपयोग ''न्यूनतम'', ''अधिकतम'' और ''औसत'' पर क्या है। आम तौर पर, जिस संसाधन पर विचार किया जा रहा है वह रनिंग टाइम है, यानी समय जटिलता, लेकिन मेमोरी या कोई अन्य संसाधन भी हो सकता है। सबसे अच्छा स्थिति वह फ़ंक्शन है जो n तत्वों के इनपुट डेटा पर न्यूनतम चरणों को निष्पादित करता है। निकृष्ट स्थिति वह फ़ंक्शन है जो आकार n के इनपुट डेटा पर अधिकतम संख्या में चरण निष्पादित करता है। औसत केस वह फ़ंक्शन है जो n तत्वों के इनपुट डेटा पर औसत चरणों की संख्या निष्पादित करता है।
कंप्यूटर विज्ञान में, किसी दिए गए एल्गोरिदम के '''सर्वोत्तम''', '''निकृष्ट''' और '''औसत''' स्थिति क्रमशः यह व्यक्त करते हैं कि संसाधन का उपयोग ''न्यूनतम'', ''अधिकतम'' और ''औसत'' पर क्या है। सामान्यतः, जिस संसाधन पर विचार किया जा रहा है वह रनिंग टाइम है, यानी समय जटिलता, लेकिन मेमोरी या कोई अन्य संसाधन भी हो सकता है। सबसे अच्छा स्थिति वह फ़ंक्शन है जो n घटकों के इनपुट डेटा पर न्यूनतम चरणों को निष्पादित करता है। निकृष्ट स्थिति वह फ़ंक्शन है जो आकार n के इनपुट डेटा पर अधिकतम संख्या में चरण निष्पादित करता है। औसत केस वह फ़ंक्शन है जो n घटकों के इनपुट डेटा पर औसत चरणों की संख्या निष्पादित करता है।


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


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


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


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


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


''विशिष्ट इनपुट'' का क्या मतलब है यह निर्धारित करना कठिन है, और अक्सर उस औसत इनपुट में ऐसे गुण होते हैं जो गणितीय रूप से वर्णन करना कठिन बनाते हैं (उदाहरण के लिए, एल्गोरिदम पर विचार करें जो पाठ के [[स्ट्रिंग (कंप्यूटर विज्ञान)|स्ट्रिंग]] पर काम करने के लिए डिज़ाइन किए गए हैं)। इसी तरह, जब किसी विशेष "औसत मामले" (जो संभवतः केवल एल्गोरिथ्म के कुछ उपयोगों के लिए लागू होगा) का एक समझदार विवरण संभव है, तो उनके परिणामस्वरूप समीकरणों का अधिक कठिन विश्लेषण होता है।<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>{{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>
== व्यावहारिक परिणाम ==
== व्यावहारिक परिणाम ==
खराब निकृष्ट स्थिति वाले प्रदर्शन वाले कई एल्गोरिदम का औसत-स्थिति प्रदर्शन अच्छा होता है। जिन समस्याओं को हम हल करना चाहते हैं, उनके लिए यह एक अच्छी बात है: हम आशा कर सकते हैं कि जिन विशेष उदाहरणों की हमें परवाह है वे औसत हों। [[क्रिप्टोग्राफी]] के लिए, यह बहुत खराब है: हम चाहते हैं कि क्रिप्टोग्राफ़िक समस्या के विशिष्ट उदाहरण कठिन हों। यहां कुछ विशिष्ट समस्याओं के लिए रैंडम सेल्फ-रिड्यूसिबिलिटी जैसी विधियों का उपयोग यह दिखाने के लिए किया जा सकता है कि सबसे खराब मामला औसत मामले की तुलना में कठिन नहीं है, या, समकक्ष, कि औसत मामला सबसे खराब मामले की तुलना में आसान नहीं है।
खराब निकृष्ट स्थिति वाले प्रदर्शन वाले कई एल्गोरिदम का औसत-स्थिति प्रदर्शन अच्छा होता है। जिन समस्याओं को हम हल करना चाहते हैं, उनके लिए यह एक अच्छी बात है: हम आशा कर सकते हैं कि जिन विशेष उदाहरणों की हमें परवाह है वे औसत हों। [[क्रिप्टोग्राफी]] के लिए, यह बहुत खराब है: हम चाहते हैं कि क्रिप्टोग्राफ़िक समस्या के विशिष्ट उदाहरण कठिन हों। यहां कुछ विशिष्ट समस्याओं के लिए रैंडम सेल्फ-रिड्यूसिबिलिटी जैसी विधियों का उपयोग यह दिखाने के लिए किया जा सकता है कि सबसे खराब स्तिथि औसत स्तिथि की तुलना में कठिन नहीं है, या, समकक्ष, कि औसत स्तिथि सबसे खराब स्तिथि की तुलना में आसान नहीं है।


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


== उदाहरण ==
== उदाहरण ==
Line 56: 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 100: 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’