View source for एल्गोरिदम का विश्लेषण

{{Short description|Study of resources used by an algorithm}}
{{more footnotes|date=March 2010}}
[[File:Binary search vs Linear search example svg.svg|thumb|दी गई क्रमित सूची में दी गई प्रविष्टि को देखने के लिए, [[द्विआधारी खोज एल्गोरिथ्म]] और [[रैखिक खोज]] एल्गोरिथम (जो ऑर्डरिंग पर ध्यान नहीं देता) दोनों का उपयोग किया जा सकता है। पूर्व और बाद वाले एल्गोरिदम के विश्लेषण से पता चलता है कि यह अधिक से अधिक लेता है {{math|log<sub>2</sub> ''n''}} और {{mvar|''n''}} आकार की सूची के लिए क्रमशः चरणों की जाँच करें {{mvar|''n''}}. आकार 33 की चित्रित उदाहरण सूची में, मोरिन की खोज में, आर्थर बाइनरी के साथ 5 और 28 कदम उठाता है (में दिखाया गया है) {{color|#008080|cyan}}) और रैखिक ({{color|#800080|magenta}}) क्रमशः खोजें।]]
[[File:comparison_computational_complexity.svg|thumb|एल्गोरिदम के विश्लेषण में आमतौर पर उपयोग किए जाने वाले कार्यों के ग्राफ़, संचालन की संख्या दिखाते हैं {{mvar|''N''}} बनाम इनपुट आकार {{mvar|''n''}} प्रत्येक समारोह के लिए]][[कंप्यूटर विज्ञान]] में, एल्गोरिदम का विश्लेषण एल्गोरिदम की कम्प्यूटेशनल जटिलता को खोजने की प्रक्रिया है - उन्हें निष्पादित करने के लिए आवश्यक समय, भंडारण या अन्य संसाधनों की मात्रा। आमतौर पर, इसमें एक फ़ंक्शन (गणित) का निर्धारण करना शामिल होता है जो एक एल्गोरिथ्म के इनपुट के आकार को उसके द्वारा उठाए जाने वाले कदमों की संख्या (इसकी [[समय जटिलता]]) या इसके द्वारा उपयोग किए जाने वाले भंडारण स्थानों की संख्या (इसकी [[अंतरिक्ष जटिलता]]) से संबंधित करता है। एक एल्गोरिदम कुशल कहा जाता है जब इस फ़ंक्शन के मान छोटे होते हैं, या इनपुट के आकार में वृद्धि की तुलना में धीरे-धीरे बढ़ते हैं। एक ही आकार के अलग-अलग इनपुट के कारण एल्गोरिथम का अलग व्यवहार हो सकता है, इसलिए सर्वोत्तम, सबसे खराब और औसत केस विवरण सभी व्यावहारिक रुचि के हो सकते हैं। जब अन्यथा निर्दिष्ट नहीं किया जाता है, तो एल्गोरिथ्म के प्रदर्शन का वर्णन करने वाला फ़ंक्शन आमतौर पर एक [[ऊपरी सीमा]] होती है, जो कि एल्गोरिथम के सबसे खराब स्थिति इनपुट से निर्धारित होती है।

एल्गोरिदम का शब्द विश्लेषण [[डोनाल्ड नुथ]] द्वारा गढ़ा गया था।<ref>{{cite web|url=http://www-cs-faculty.stanford.edu/~uno/news.html|archive-url=https://web.archive.org/web/20160828152021/http://www-cs-faculty.stanford.edu/~uno/news.html|url-status=dead|archive-date=28 August 2016|title=Knuth: Recent News|date=28 August 2016}}</ref> एल्गोरिथ्म विश्लेषण व्यापक [[कम्प्यूटेशनल जटिलता सिद्धांत]] का एक महत्वपूर्ण हिस्सा है, जो किसी भी एल्गोरिदम द्वारा आवश्यक संसाधनों के लिए सैद्धांतिक अनुमान प्रदान करता है जो किसी दिए गए [[कम्प्यूटेशनल समस्या]] को हल करता है। ये अनुमान [[एल्गोरिथम दक्षता]] के लिए खोज की उचित दिशाओं में अंतर्दृष्टि प्रदान करते हैं।

एल्गोरिदम के सैद्धांतिक विश्लेषण में उनकी जटिलता का आकलन असिम्प्टोटिक अर्थ में करना आम है, यानी मनमाने ढंग से बड़े इनपुट के लिए जटिलता फ़ंक्शन का अनुमान लगाना। इसके लिए [[बिग ओ नोटेशन]], [[बिग-ओमेगा नोटेशन]] और [[बिग-थीटा संकेतन]] का उपयोग किया जाता है। उदाहरण के लिए, बाइनरी खोज को आकार के लघुगणक के समानुपाती कई चरणों में चलाने के लिए कहा जाता है {{mvar|''n''}} खोजी जा रही क्रमबद्ध सूची का, या में {{math|''O''(log ''n'')}}, [[लघुगणकीय समय]] में बोलचाल की भाषा में। आमतौर पर [[स्पर्शोन्मुख विश्लेषण]] अनुमानों का उपयोग किया जाता है क्योंकि एक ही एल्गोरिथ्म के विभिन्न [[कार्यान्वयन]] दक्षता में भिन्न हो सकते हैं। हालांकि किसी दिए गए एल्गोरिथम के किसी भी दो उचित कार्यान्वयन की क्षमता एक निरंतर गुणक कारक से संबंधित होती है जिसे एक छिपा हुआ स्थिरांक कहा जाता है।

दक्षता के सटीक (असिम्प्टोटिक नहीं) उपायों की कभी-कभी गणना की जा सकती है लेकिन उन्हें आमतौर पर एल्गोरिथम के विशेष कार्यान्वयन से संबंधित कुछ मान्यताओं की आवश्यकता होती है, जिन्हें [[गणना का मॉडल]] कहा जाता है। संगणना के एक मॉडल को [[अमूर्त मशीन]] के संदर्भ में परिभाषित किया जा सकता है, उदा। [[ट्यूरिंग मशीन]], और/या यह मानकर कि कुछ ऑपरेशन यूनिट समय में निष्पादित किए जाते हैं।
उदाहरण के लिए, यदि क्रमबद्ध सूची जिसमें हम बाइनरी खोज लागू करते हैं {{mvar|''n''}} तत्व, और हम गारंटी दे सकते हैं कि सूची में किसी तत्व का प्रत्येक लुकअप इकाई समय में किया जा सकता है, फिर अधिकतम {{math|log<sub>2</sub>(''n'') + 1}} उत्तर देने के लिए समय इकाइयों की आवश्यकता होती है।
<!-- Exact measures of efficiency are useful to the people who actually implement and use algorithms, because they are more precise and thus enable them to know how much time they can expect to spend in execution. To some people (e.g. game programmers), a hidden constant can make all the difference between success and failure.-->


== लागत मॉडल ==
समय दक्षता का अनुमान इस बात पर निर्भर करता है कि हम एक चरण के रूप में क्या परिभाषित करते हैं। विश्लेषण के लिए वास्तविक रन-टाइम के लिए उपयोगी रूप से अनुरूप होने के लिए, एक चरण को पूरा करने के लिए आवश्यक समय को एक स्थिरांक के ऊपर बाध्य होने की गारंटी दी जानी चाहिए। यहाँ सावधान रहना चाहिए; उदाहरण के लिए, कुछ विश्लेषण दो संख्याओं के जोड़ को एक चरण के रूप में गिनते हैं। यह धारणा कुछ संदर्भों में वारंट नहीं हो सकती है। उदाहरण के लिए, यदि गणना में शामिल संख्याएँ मनमाने ढंग से बड़ी हो सकती हैं, तो एक जोड़ के लिए आवश्यक समय को स्थिर नहीं माना जा सकता है।

दो लागत मॉडल आम तौर पर उपयोग किए जाते हैं:<ref name="AhoHopcroft1974">{{cite book|author1=Alfred V. Aho|author2=John E. Hopcroft|author3=Jeffrey D. Ullman|title=The design and analysis of computer algorithms|url=https://archive.org/details/designanalysisof00ahoarich|url-access=registration|year=1974|publisher=Addison-Wesley Pub. Co.|isbn=9780201000290}}, section 1.3</ref><ref name="Hromkovič2004">{{cite book|author=Juraj Hromkovič|title=सैद्धांतिक कंप्यूटर विज्ञान: ऑटोमेटा, कम्प्यूटेबिलिटी, जटिलता, एल्गोरिथम, यादृच्छिककरण, संचार और क्रिप्टोग्राफी का परिचय|url=https://books.google.com/books?id=KpNet-n262QC&pg=PA177|year=2004|publisher=Springer|isbn=978-3-540-14015-3|pages=177–178}}</रेफरी><ref name="Ausiello1999">{{cite book|author=Giorgio Ausiello|title=Complexity and approximation: combinatorial optimization problems and their approximability properties|url=https://books.google.com/books?id=Yxxw90d9AuMC&pg=PA3|year=1999|publisher=Springer|isbn=978-3-540-65431-5|pages=3–8}}</ref><ref name=Wegener20>{{Citation|last1=Wegener|first1=Ingo|title=Complexity theory: exploring the limits of efficient algorithms|publisher=[[Springer-Verlag]]|location=Berlin, New York|isbn=978-3-540-21045-0|year=2005|page=20|url=https://books.google.com/books?id=u7DZSDSUYlQC&pg=PA20}}</ref><ref name="Tarjan1983">{{cite book|author=Robert Endre Tarjan|author-link=Robert Endre Tarjan|title=Data structures and network algorithms|url=https://books.google.com/books?id=JiC7mIqg-X4C&pg=PA3|year=1983|publisher=SIAM|isbn=978-0-89871-187-5|pages=3–7}}</ref>
* यूनिफ़ॉर्म कॉस्ट मॉडल, जिसे यूनिफ़ॉर्म-कॉस्ट मेजरमेंट (और इसी तरह की विविधताएं) भी कहा जाता है, इसमें शामिल संख्याओं के आकार की परवाह किए बिना, हर मशीन के संचालन के लिए एक स्थिर लागत प्रदान करता है।
* लघुगणक लागत मॉडल, जिसे लघुगणक-लागत माप (और इसी तरह की विविधताएं) भी कहा जाता है, शामिल बिट्स की संख्या के अनुपात में प्रत्येक मशीन संचालन के लिए लागत निर्दिष्ट करता है

उत्तरार्द्ध उपयोग करने के लिए अधिक बोझिल है, इसलिए यह केवल तभी नियोजित होता है जब आवश्यक हो, उदाहरण के लिए मनमाना-परिशुद्धता अंकगणितीय एल्गोरिदम के विश्लेषण में, जैसे कि [[क्रिप्टोग्राफी]] में उपयोग किया जाता है।

एक महत्वपूर्ण बिंदु जिसे अक्सर अनदेखा किया जाता है वह यह है कि समस्याओं के लिए प्रकाशित निचली सीमाएं अक्सर गणना के मॉडल के लिए दी जाती हैं जो संचालन के सेट से अधिक प्रतिबंधित होती है जिसे आप अभ्यास में उपयोग कर सकते हैं और इसलिए ऐसे एल्गोरिदम हैं जो भोलेपन की तुलना में तेज़ हैं संभव सोचा।<ref>[https://cstheory.stackexchange.com/q/608 Examples of the price of abstraction?], cstheory.stackexchange.com</ref>


== रन-टाइम विश्लेषण ==
रन-टाइम विश्लेषण एक सैद्धांतिक वर्गीकरण है जो एक [[कलन विधि]] के [[DTIME]] (या रन-टाइम या निष्पादन समय) में इसकी [[जानकारी]] के रूप में वृद्धि का अनुमान लगाता है और अनुमान लगाता है (आमतौर पर इसके रूप में दर्शाया जाता है) {{mvar|''n''}}) बढ़ती है। कंप्यूटर विज्ञान में रन-टाइम दक्षता बहुत रुचि का विषय है: एक [[कंप्यूटर प्रोग्राम]] को क्रियान्वित करने में सेकंड, घंटे या साल भी लग सकते हैं, यह इस बात पर निर्भर करता है कि यह किस एल्गोरिथम को लागू करता है। जबकि [[सॉफ्टवेयर प्रोफाइलिंग]] तकनीकों का उपयोग व्यवहार में एक एल्गोरिथम के रन-टाइम को मापने के लिए किया जा सकता है, वे असीम रूप से कई संभावित इनपुट के लिए समय डेटा प्रदान नहीं कर सकते हैं; उत्तरार्द्ध केवल रन-टाइम विश्लेषण के सैद्धांतिक तरीकों से प्राप्त किया जा सकता है।

=== अनुभवजन्य मेट्रिक्स की कमियां ===

चूंकि एल्गोरिदम प्लेटफ़ॉर्म-स्वतंत्र हैं (यानी किसी दिए गए एल्गोरिदम को मनमाने ढंग से [[ऑपरेटिंग सिस्टम]] चलाने वाले मनमाने ढंग से [[कंप्यूटर]] पर मनमाने ढंग से [[प्रोग्रामिंग भाषा]] में लागू किया जा सकता है), दिए गए सेट के तुलनात्मक प्रदर्शन को मापने के लिए एक अनुभवजन्य दृष्टिकोण का उपयोग करने के लिए अतिरिक्त महत्वपूर्ण कमियां हैं एल्गोरिदम।

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

{| class="wikitable"
|-
! ''n'' (list size)
! Computer A run-time<br />(in [[nanosecond]]s)
! Computer B run-time<br />(in [[nanosecond]]s)
|-
| 16
| 8 
| 100,000 
|-
| 63
| 32 
| 150,000 
|-
| 250
| 125 
| 200,000 
|-
| 1,000
| 500 
| 250,000 
|}
इन मेट्रिक्स के आधार पर, यह निष्कर्ष निकालना आसान होगा कि कंप्यूटर ए एक एल्गोरिदम चला रहा है जो कंप्यूटर बी की तुलना में दक्षता में कहीं बेहतर है। हालांकि, यदि इनपुट-सूची का आकार पर्याप्त संख्या में बढ़ाया जाता है, उस निष्कर्ष को नाटकीय रूप से त्रुटि के रूप में प्रदर्शित किया गया है:

{| class="wikitable"
|-
! ''n'' (list size)
! Computer A run-time<br />(in [[nanosecond]]s)
! Computer B run-time<br />(in [[nanosecond]]s)
|-
| 16
| 8 
| 100,000 
|-
| 63
| 32 
| 150,000 
|-
| 250
| 125 
| 200,000 
|-
| 1,000
| 500 
| 250,000 
|-
| ...
| ...
| ...
|-
| 1,000,000
| 500,000
| 500,000
|-
| 4,000,000
| 2,000,000
| 550,000
|-
| 16,000,000
| 8,000,000
| 600,000
|-
| ...
| ...
| ...
|-
| 63,072 &times; 10<sup>12</sup>
| 31,536 &times; 10<sup>12</sup> ns,<br />or 1 year
| 1,375,000 ns,<br />or 1.375 milliseconds
|}
कंप्यूटर ए, रैखिक खोज कार्यक्रम चला रहा है, एक रैखिक विकास दर प्रदर्शित करता है। प्रोग्राम का रन-टाइम इसके इनपुट आकार के सीधे आनुपातिक है। इनपुट आकार को दोगुना करने से रन-टाइम दोगुना हो जाता है, इनपुट आकार को चौगुना करने से रन-टाइम चौगुना हो जाता है, और इसी तरह। दूसरी ओर, कंप्यूटर बी, बाइनरी सर्च प्रोग्राम चला रहा है, एक लॉगरिदमिक विकास दर प्रदर्शित करता है। इनपुट आकार को चौगुना करने से विक्षनरी द्वारा केवल रन-टाइम बढ़ता है: लगातार राशि (इस उदाहरण में, 50,000 एनएस)। भले ही कंप्यूटर ए जाहिरा तौर पर एक तेज़ मशीन है, कंप्यूटर बी रन-टाइम में अनिवार्य रूप से कंप्यूटर ए से आगे निकल जाएगा क्योंकि यह बहुत धीमी विकास दर के साथ एक एल्गोरिथम चला रहा है।

=== वृद्धि के क्रम ===
{{main|Big O notation}}
अनौपचारिक रूप से, एक एल्गोरिदम को एक निश्चित इनपुट आकार से परे एक फ़ंक्शन (गणित) के आदेश पर विकास दर प्रदर्शित करने के लिए कहा जा सकता है। {{mvar|''n''}}, कार्यक्रम {{math|''f''(''n'')}} बार एक सकारात्मक स्थिरांक उस एल्गोरिथम के रन-टाइम के लिए एक स्पर्शोन्मुख विश्लेषण प्रदान करता है। दूसरे शब्दों में, दिए गए इनपुट आकार के लिए {{mvar|''n''}} कुछ से बड़ा {{mvar|''n''}}<sub>0</sub> और एक स्थिर {{mvar|''c''}}, उस एल्गोरिथम का रन-टाइम इससे बड़ा कभी नहीं होगा {{math|''c'' × ''f''(''n'')}}. यह अवधारणा अक्सर बिग ओ नोटेशन का उपयोग करके व्यक्त की जाती है। उदाहरण के लिए, चूंकि [[सम्मिलन सॉर्ट]] का रन-टाइम [[द्विघात वृद्धि]] करता है क्योंकि इसका इनपुट आकार बढ़ता है, इंसर्शन सॉर्ट को ऑर्डर का कहा जा सकता है {{math|''O''(''n''<sup>2</sup>)}}.

बिग ओ नोटेशन सर्वश्रेष्ठ, सबसे खराब और औसत मामले को व्यक्त करने का एक सुविधाजनक तरीका है। किसी दिए गए एल्गोरिथ्म के लिए सबसे खराब स्थिति, हालांकि इसका उपयोग औसत-केस को व्यक्त करने के लिए भी किया जा सकता है - उदाहरण के लिए, [[जल्दी से सुलझाएं]] के लिए सबसे खराब स्थिति है {{math|''O''(''n''<sup>2</sup>)}}, लेकिन औसत-केस रन-टाइम है {{math|''O''(''n'' log ''n'')}}.

=== विकास के अनुभवजन्य आदेश ===
रन-टाइम मानते हुए शक्ति नियम का पालन करता है, {{math|''t'' &asymp; ''kn''<sup>''a''</sup>}}, गुणांक {{mvar|''a''}} पाया जा सकता है <ref>[http://rjlipton.wordpress.com/2009/07/24/how-to-avoid-o-abuse-and-bribes/ How To Avoid O-Abuse and Bribes] {{Webarchive|url=https://web.archive.org/web/20170308175036/https://rjlipton.wordpress.com/2009/07/24/how-to-avoid-o-abuse-and-bribes/ |date=2017-03-08 }}, at the blog "Gödel's Lost Letter and P=NP" by R. J. Lipton, professor of Computer Science at Georgia Tech, recounting idea by Robert Sedgewick</ref> रन-टाइम के अनुभवजन्य मापन द्वारा {{math|{''t''<sub>1</sub>, ''t''<sub>2</sub>}}} कुछ समस्या-आकार बिंदुओं पर {{math|{''n''<sub>1</sub>, ''n''<sub>2</sub>}}}, और गणना {{math|1=''t''<sub>2</sub>/''t''<sub>1</sub> = (''n''<sub>2</sub>/''n''<sub>1</sub>)<sup>''a''</sup>}} ताकि {{math|1=''a'' = log(''t''<sub>2</sub>/''t''<sub>1</sub>)/log(''n''<sub>2</sub>/''n''<sub>1</sub>)}}. दूसरे शब्दों में, यह कुछ आकार बिंदु पर रन-टाइम बनाम इनपुट आकार के लॉग-लॉग प्लॉट पर अनुभवजन्य रेखा के ढलान को मापता है। यदि विकास का क्रम वास्तव में शक्ति नियम का पालन करता है (और इसलिए लॉग-लॉग प्लॉट पर रेखा वास्तव में एक सीधी रेखा है), का अनुभवजन्य मूल्य {{mvar||''a''}} विभिन्न श्रेणियों पर स्थिर रहेगा, और यदि नहीं, तो यह बदल जाएगा (और रेखा एक घुमावदार रेखा है) - लेकिन फिर भी विकास व्यवहार के उनके अनुभवजन्य स्थानीय आदेशों के रूप में किसी भी दो एल्गोरिदम की तुलना करने के लिए काम कर सकता है। उपरोक्त तालिका पर लागू:

{| class="wikitable"
|-_
! ''n'' (list size)
! Computer A run-time<br />(in [[nanosecond]]s)
! Local order of growth<br />(n^_)
! Computer B run-time<br />(in [[nanosecond]]s)
! Local order of growth<br />(n^_)
|-
| 15
| 7 
| 
| 100,000 
| 
|-
| 65
| 32 
| 1.04
| 150,000 
| 0.28
|-
| 250
| 125 
| 1.01
| 200,000 
| 0.21
|-
| 1,000
| 500 
| 1.00
| 250,000 
| 0.16
|-
| ...
| ...
| 
| ...
| 
|-
| 1,000,000
| 500,000
| 1.00
| 500,000
| 0.10
|-
| 4,000,000
| 2,000,000
| 1.00
| 550,000
| 0.07
|-
| 16,000,000
| 8,000,000
| 1.00
| 600,000
| 0.06
|-
| ...
| ...
| 
| ...
| 
|}
यह स्पष्ट रूप से देखा गया है कि पहला एल्गोरिथ्म वास्तव में शक्ति नियम का पालन करते हुए विकास के एक रेखीय क्रम को प्रदर्शित करता है। दूसरे के लिए अनुभवजन्य मूल्य तेजी से कम हो रहे हैं, यह सुझाव दे रहा है कि यह विकास के एक और नियम का पालन करता है और किसी भी मामले में पहले की तुलना में विकास के स्थानीय क्रम (और अभी भी सुधार) बहुत कम है।

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

 1 इनपुट से धनात्मक पूर्णांक n प्राप्त करें
 2 'अगर' एन> 10
 3 'प्रिंट' इसमें कुछ समय लग सकता है...
 4 'के लिए' मैं = 1 'से' एन
 5 'के लिए' जे = 1 'से' मैं
 6 'प्रिंट' आई * जे
 7 'प्रिंट' हो गया!

इस एल्गोरिथम को पूरा करने में शामिल प्रत्येक [[निर्देश (कंप्यूटर विज्ञान)]] को निष्पादित करने के लिए एक दिया गया कंप्यूटर एक DTIME लेगा। किसी दिए गए निर्देश को पूरा करने के लिए विशिष्ट समय अलग-अलग होगा, इस पर निर्भर करता है कि कौन सा निर्देश निष्पादित किया जा रहा है और कौन सा कंप्यूटर इसे निष्पादित कर रहा है, लेकिन एक पारंपरिक कंप्यूटर पर, यह राशि [[नियतात्मक प्रणाली (गणित)]] होगी।<ref>However, this is not the case with a [[quantum computer]]</ref> कहें कि चरण 1 में किए गए कार्यों को समय टी का उपभोग करने के लिए माना जाता है<sub>1</sub>, चरण 2 समय T का उपयोग करता है<sub>2</sub>, इत्यादि।

उपरोक्त एल्गोरिद्म में, चरण 1, 2 और 7 केवल एक बार चलाए जाएंगे। सबसे खराब स्थिति के मूल्यांकन के लिए, यह माना जाना चाहिए कि चरण 3 भी चलाया जाएगा। इस प्रकार चरण 1-3 और चरण 7 को चलाने के लिए कुल समय है:

:<math>T_1 + T_2 + T_3 + T_7. \,</math>
चरण 4, 5 और 6 में [[प्रोग्राम लूप]] का मूल्यांकन करना कठिन है। चरण 4 में बाहरी पाश परीक्षण निष्पादित होगा (n + 1)
टाइम्स (ध्यान दें कि लूप को समाप्त करने के लिए एक अतिरिक्त चरण की आवश्यकता है, इसलिए n + 1 और n निष्पादन नहीं), जो T का उपभोग करेगा<sub>4</sub>(एन + 1) समय। दूसरी ओर, आंतरिक पाश, j के मान द्वारा शासित होता है, जो 1 से i तक चलता है। बाहरी लूप के पहले पास पर, j 1 से 1 तक दोहराता है: आंतरिक लूप एक पास बनाता है, इसलिए आंतरिक लूप बॉडी (चरण 6) को चलाने से T की खपत होती है<sub>6</sub> समय, और इनर लूप टेस्ट (चरण 5) 2T की खपत करता है<sub>5</sub> समय। बाहरी लूप के माध्यम से अगले पास के दौरान, j 1 से 2 तक पुनरावृत्त होता है: आंतरिक लूप दो पास बनाता है, इसलिए आंतरिक लूप बॉडी (चरण 6) को चलाने से 2T की खपत होती है<sub>6</sub> समय, और इनर लूप टेस्ट (चरण 5) में 3T की खपत होती है<sub>5</sub> समय।

कुल मिलाकर, आंतरिक लूप बॉडी को चलाने के लिए आवश्यक कुल समय [[अंकगणितीय प्रगति]] के रूप में व्यक्त किया जा सकता है:

:<math>T_6 + 2T_6 + 3T_6 + \cdots + (n-1) T_6 + n T_6</math>
जो [[गुणन]]खंड हो सकता है<ref>It can be proven by [[Mathematical induction|induction]] that <math>1 + 2 + 3 + \cdots + (n-1) + n = \frac{n(n+1)}{2}</math></ref> जैसा

:<math>\left[ 1 + 2 + 3 + \cdots + (n-1) + n \right] T_6 = \left[ \frac{1}{2} (n^2 + n) \right] T_6</math>
बाहरी पाश परीक्षण चलाने के लिए आवश्यक कुल समय का मूल्यांकन इसी प्रकार किया जा सकता है:

:<math>\begin{align}
& 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1) T_5 + n T_5 + (n + 1) T_5\\
=\ &T_5 + 2T_5 + 3T_5 + 4T_5 + \cdots + (n-1)T_5 + nT_5 + (n+1)T_5 - T_5
\end{align}</math>
जिसे इस रूप में गिना जा सकता है

:<math>\begin{align}
& T_5 \left[ 1+2+3+\cdots + (n-1) + n + (n + 1) \right] - T_5 \\
=& \left[ \frac{1}{2} (n^2 + n) \right] T_5 + (n + 1)T_5 - T_5 \\
=& \left[ \frac{1}{2} (n^2 + n) \right] T_5 + n T_5 \\
=& \left[ \frac{1}{2} (n^2 + 3n) \right] T_5
\end{align}</math>
इसलिए, इस एल्गोरिथम के लिए कुल रन-टाइम है:

:<math>f(n) = T_1 + T_2 + T_3 + T_7 + (n + 1)T_4 + \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2+3n) \right] T_5</math>
जो कम हो जाता है

:<math>f(n) = \left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7</math>
अंगूठे के नियम के रूप में, कोई यह मान सकता है कि किसी दिए गए फ़ंक्शन में उच्चतम क्रम का शब्द विकास की दर पर हावी है और इस प्रकार इसके रन-टाइम ऑर्डर को परिभाषित करता है। इस उदाहरण में, एन<sup>2</sup> उच्चतम क्रम वाला शब्द है, इसलिए कोई यह निष्कर्ष निकाल सकता है {{math|1=''f''(''n'') = ''O''(''n''<sup>2</sup>)}}. औपचारिक रूप से इसे इस प्रकार सिद्ध किया जा सकता है:
{{quote|Prove that <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2,\ n \ge n_0</math>
<br /><br />
<math>\begin{align}
&\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7\\
\le &( n^2 + n )T_6 + ( n^2 + 3n )T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \ (\text{for } n \ge 0 )
\end{align}</math>
<br /><br />
Let ''k'' be a constant greater than or equal to [''T''<sub>1</sub>..''T''<sub>7</sub>]
<br /><br />
<math>\begin{align}
&T_6( n^2 + n ) + T_5( n^2 + 3n ) + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le k( n^2 + n ) + k( n^2 + 3n ) + kn + 5k\\
= &2kn^2 + 5kn + 5k \le 2kn^2 + 5kn^2 + 5kn^2 \ (\text{for } n \ge 1) = 12kn^2
\end{align}</math>
<br /><br />
Therefore <math>\left[ \frac{1}{2} (n^2 + n) \right] T_6 + \left[ \frac{1}{2} (n^2 + 3n) \right] T_5 + (n + 1)T_4 + T_1 + T_2 + T_3 + T_7 \le cn^2, n \ge n_0 \text{ for } c = 12k, n_0 = 1</math>
}}
इस एल्गोरिदम का विश्लेषण करने के लिए एक और [[लालित्य]] दृष्टिकोण यह घोषित करना होगा कि [टी<sub>1</sub>..टी<sub>7</sub>] चुनी गई इकाइयों की प्रणाली में सभी समय की एक इकाई के बराबर हैं ताकि इन चरणों के लिए एक इकाई वास्तविक समय से अधिक या उसके बराबर हो। इसका मतलब यह होगा कि एल्गोरिथम का रन-टाइम निम्नानुसार टूट जाता है:<ref>This approach, unlike the above approach, neglects the constant time consumed by the loop tests which terminate their respective loops, but it is [[Trivial (mathematics)|trivial]] to prove that such omission does not affect the final result</ref>
{{quote|<math>4+\sum_{i=1}^n i\leq 4+\sum_{i=1}^n n=4+n^2\leq5n^2 \ (\text{for } n \ge 1) =O(n^2).</math>}}


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

 जबकि ''फ़ाइल अभी भी खुली है:''
     चलो n = ''फ़ाइल का आकार''
     ''फ़ाइल आकार में वृद्धि के प्रत्येक 100,000 [[किलोबाइट]]'' के लिए
         ''आरक्षित स्मृति की दुगुनी मात्रा''

इस उदाहरण में, जैसे ही फ़ाइल का आकार n बढ़ता है, स्मृति एक [[घातीय वृद्धि]] दर पर उपभोग की जाएगी, जो क्रम है {{math|''O''(2<sup>''n''</sup>)}}. यह स्मृति [[संसाधन (कंप्यूटर विज्ञान)]] की खपत के लिए एक अत्यंत तीव्र और सबसे अधिक संभावना असहनीय विकास दर है।

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

== निरंतर कारक ==
एल्गोरिदम का विश्लेषण आम तौर पर स्पर्शोन्मुख प्रदर्शन पर ध्यान केंद्रित करता है, विशेष रूप से प्राथमिक स्तर पर, लेकिन व्यावहारिक अनुप्रयोगों में निरंतर कारक महत्वपूर्ण होते हैं, और वास्तविक दुनिया का डेटा व्यवहार में हमेशा आकार में सीमित होता है। सीमा आमतौर पर एड्रेसेबल मेमोरी के आकार की होती है, इसलिए 32-बिट मशीनों पर 2<sup>32</sup> = 4 GiB (यदि खंडित मेमोरी का उपयोग किया जाता है तो अधिक) और 64-बिट मशीनों पर 2<sup>64</sup> = 16 ईआईबी। इस प्रकार एक सीमित आकार दिया गया है, विकास का क्रम (समय या स्थान) एक स्थिर कारक द्वारा प्रतिस्थापित किया जा सकता है, और इस अर्थ में सभी व्यावहारिक एल्गोरिदम हैं {{math|''O''(1)}} पर्याप्त बड़े स्थिरांक के लिए, या पर्याप्त छोटे डेटा के लिए।

यह व्याख्या उन कार्यों के लिए मुख्य रूप से उपयोगी है जो बेहद धीमी गति से बढ़ते हैं: (बाइनरी) [[पुनरावृत्त लघुगणक]] (log<sup>*</sup>) सभी व्यावहारिक डेटा के लिए 5 से कम है (2<sup>65536</sup> बिट्स); (बाइनरी) लॉग-लॉग (लॉग लॉग एन) वस्तुतः सभी व्यावहारिक डेटा के लिए 6 से कम है (2<sup>64</sup> बिट्स); और वस्तुतः सभी व्यावहारिक डेटा के लिए बाइनरी लॉग (लॉग एन) 64 से कम है (2<sup>64</sup> बिट्स)। गैर-निरंतर जटिलता वाला एक एल्गोरिथम फिर भी व्यावहारिक डेटा पर निरंतर जटिलता वाले एल्गोरिथम की तुलना में अधिक कुशल हो सकता है यदि निरंतर समय एल्गोरिथम के ओवरहेड के परिणामस्वरूप एक बड़ा स्थिर कारक होता है, उदाहरण के लिए, एक हो सकता है <math>K > k \log \log n</math> जब तक <math>K/k > 6</math> और <math>n < 2^{2^6} = 2^{64}</math>.

बड़े डेटा के लिए रैखिक या द्विघात कारकों को नजरअंदाज नहीं किया जा सकता है, लेकिन छोटे डेटा के लिए एक असम्बद्ध रूप से अक्षम एल्गोरिदम अधिक कुशल हो सकता है। यह विशेष रूप से [[हाइब्रिड एल्गोरिदम]] में उपयोग किया जाता है, जैसे [[टिमसोर्ट]], जो एक एसिम्प्टोटिक रूप से कुशल एल्गोरिदम का उपयोग करते हैं (यहां समय जटिलता के साथ [[मर्ज़ सॉर्ट]] करें) <math>n \log n</math>), लेकिन समय जटिलता के साथ एक असम्बद्ध रूप से अक्षम एल्गोरिदम (यहां सम्मिलन प्रकार) पर स्विच करें <math>n^2</math>) छोटे डेटा के लिए, क्योंकि सरल एल्गोरिथ्म छोटे डेटा पर तेज़ होता है।

== यह भी देखें ==
* [[परिशोधित विश्लेषण]]
* [[समानांतर एल्गोरिदम का विश्लेषण]]
* [[स्पर्शोन्मुख कम्प्यूटेशनल जटिलता]]
* सबसे अच्छा, सबसे खराब और औसत मामला
* बिग ओ नोटेशन
* कम्प्यूटेशनल जटिलता सिद्धांत
* [[मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)]]
* एनपी-पूर्ण
* [[संख्यात्मक विश्लेषण]]
* [[बहुपदी समय फलन]]
* [[कार्यक्रम अनुकूलन]]
* प्रोफाइलिंग (कंप्यूटर प्रोग्रामिंग)
* मापनीयता
* [[चिकना विश्लेषण]]
* [[समाप्ति विश्लेषण]] — यह जाँचने की उप-समस्या कि क्या कोई प्रोग्राम समाप्त होगा
* समय जटिलता - सामान्य एल्गोरिदम के लिए विकास के आदेशों की तालिका शामिल है
* [[सूचना-आधारित जटिलता]]

==टिप्पणियाँ==
{{Reflist}}


==संदर्भ==
*{{Cite book|title=An Introduction to the Analysis of Algorithms|edition=2nd|author-link=Robert Sedgewick (computer scientist)|first1=Robert|last1=Sedgewick|author-link2=Philippe Flajolet |first2=Philippe|last2=Flajolet|publisher=Addison-Wesley|year=2013|isbn=978-0-321-90575-8}}
*{{Cite book |first1=Daniel A. |last1=Greene |author-link2 = Donald Knuth|first2=Donald E. |last2=Knuth |title=Mathematics for the Analysis of Algorithms |edition=Second |publisher=Birkhäuser |year=1982 |isbn=3-7643-3102-X }}
*{{Cite book |author-link=Thomas H. Cormen |first1=Thomas H. |last1=Cormen |author-link2=Charles E. Leiserson |first2=Charles E. |last2=Leiserson |author-link3=Ronald L. Rivest |first3=Ronald L. |last3=Rivest |name-list-style=amp |author-link4=Clifford Stein |first4=Clifford |last4=Stein |title=[[Introduction to Algorithms]] |edition=Second |publisher=MIT Press and McGraw-Hill |location=Cambridge, MA |year=2001 |isbn=0-262-03293-7 |others=Chapter 1: Foundations |pages=3–122 }}
*{{Cite book |title=Algorithms in C, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching |edition=3rd |author-link=Robert Sedgewick (computer scientist) |first=Robert |last=Sedgewick |location=Reading, MA |publisher=Addison-Wesley Professional |year=1998 |isbn=978-0-201-31452-6 |url-access=registration |url=https://archive.org/details/algorithmsinc00sedg }}
*{{Cite book |title=[[The Art of Computer Programming]] |author-link=Donald Knuth |first=Donald |last=Knuth |publisher=Addison-Wesley }}
*{{Cite book |author-link=Oded Goldreich |first=Oded |last=Goldreich |title=Computational Complexity: A Conceptual Perspective |publisher=[[Cambridge University Press]] |year=2010 |isbn=978-0-521-88473-0 }}


==बाहरी संबंध==
*{{Commons category-inline}}

{{Computer science}}

{{DEFAULTSORT:Analysis Of Algorithms}}[[Category: एल्गोरिदम का विश्लेषण | एल्गोरिदम का विश्लेषण ]] [[Category: कम्प्यूटेशनल जटिलता सिद्धांत]] 



[[Category: Machine Translated Page]]
[[Category:Created On 08/02/2023]]