सबसे खराब स्थिति जटिलता: Difference between revisions

From Vigyanwiki
(Created page with "{{short description|Upper bound on resources required by an algorithm}} कंप्यूटर विज्ञान (विशेष रूप से कम्प्...")
 
No edit summary
Line 1: Line 1:
{{short description|Upper bound on resources required by an algorithm}}
{{short description|Upper bound on resources required by an algorithm}}


[[कंप्यूटर विज्ञान]] (विशेष रूप से [[कम्प्यूटेशनल जटिलता सिद्धांत]]) में, सबसे खराब स्थिति वाली जटिलता (इसे बिग-ओह (एन) द्वारा दर्शाया गया है) [[सिस्टम संसाधन]] (उदाहरण के लिए रनिंग टाइम, [[ स्मृति ]]) को मापती है, जिसे एक [[कलन विधि]] को मनमाने आकार के इनपुट की आवश्यकता होती है ( सामान्यतः के रूप में दर्शाया जाता है {{mvar|n}} [[ बिग ओ अंकन ]] में)। यह एल्गोरिथम के लिए आवश्यक संसाधनों पर ऊपरी सीमा देता है।


रनिंग टाइम के मामले में, सबसे खराब स्थिति वाली समय जटिलता किसी भी आकार के इनपुट को देखते हुए एल्गोरिदम द्वारा निष्पादित सबसे लंबे समय तक चलने वाले समय को इंगित करती है {{mvar|n}}, और इस प्रकार गारंटी देता है कि एल्गोरिदम संकेतित समयावधि में समाप्त हो जाएगा। सबसे खराब स्थिति की जटिलता के विकास के क्रम (उदाहरण के लिए रैखिक, लॉगरिदमिक विकास) का उपयोग आमतौर पर दो एल्गोरिदम की एल्गोरिदमिक दक्षता की तुलना करने के लिए किया जाता है।
कंप्यूटर विज्ञान (विशेष रूप से कम्प्यूटेशनल जटिलता सिद्धांत) में, सबसे खराब स्थिति वाली जटिलता (इसे बिग-ओह (एन) द्वारा दर्शाया गया है) उन संसाधनों (जैसे रनिंग टाइम, मेमोरी) को मापती है जिनकी एक एल्गोरिदम को इच्छानुसार आकार के इनपुट (सामान्यतः  चिह्नित) की आवश्यकता होती है स्पर्शोन्मुख संकेतन में {{mvar|n}} के रूप में)। यह एल्गोरिथम के लिए आवश्यक संसाधनों पर ऊपरी सीमा देता है।
 
रनिंग टाइम के स्थिति में, सबसे खराब स्थिति वाली समय जटिलता, आकार {{mvar|n}} के किसी भी इनपुट को देखते हुए एल्गोरिदम द्वारा निष्पादित सबसे लंबे समय तक चलने वाले समय को इंगित करती है, और इस प्रकार आश्वासन देती है कि एल्गोरिदम संकेतित समय अवधि में समाप्त हो जाएगा। सबसे खराब स्थिति की जटिलता के विकास के क्रम (जैसे रैखिक, लघुगणक) का उपयोग सामान्यतः दो एल्गोरिदम की दक्षता की तुलना करने के लिए किया जाता है।


किसी एल्गोरिदम की सबसे खराब स्थिति वाली जटिलता की तुलना उसकी औसत-केस जटिलता से की जानी चाहिए, जो कि यादृच्छिक इनपुट पर एल्गोरिदम द्वारा उपयोग किए जाने वाले संसाधनों की मात्रा का औसत माप है।
किसी एल्गोरिदम की सबसे खराब स्थिति वाली जटिलता की तुलना उसकी औसत-केस जटिलता से की जानी चाहिए, जो कि यादृच्छिक इनपुट पर एल्गोरिदम द्वारा उपयोग किए जाने वाले संसाधनों की मात्रा का औसत माप है।


== परिभाषा ==
== परिभाषा ==
गणना का एक मॉडल और एक एल्गोरिदम दिया गया है <math>\mathsf{A}</math> जो प्रत्येक इनपुट पर रुकता है <math>s</math>, मानचित्रण <math>t_{\mathsf{A}} \colon \{0, 1\}^\star \to \N</math> की समय जटिलता कहलाती है <math>\mathsf{A}</math> यदि, प्रत्येक कम्प्यूटेशनल जटिलता सिद्धांत के लिए#समस्या उदाहरणों का प्रतिनिधित्व <math>s</math>, <math>\mathsf{A}</math> ठीक बाद रुकता है <math>t_{\mathsf{A}}(s)</math> कदम।
गणना के एक मॉडल और एक एल्गोरिदम <math>\mathsf{A}</math> को देखते हुए जो प्रत्येक इनपुट <math>s</math> पर रुकता है, मैपिंग <math>t_{\mathsf{A}} \colon \{0, 1\}^\star \to \N</math> को <math>\mathsf{A}</math>की समय जटिलता कहा जाता है, यदि प्रत्येक इनपुट स्ट्रिंग <math>s</math> के लिए, <math>\mathsf{A}</math>} ठीक <math>t_{\mathsf{A}}(s)</math> चरणों के बाद रुक जाता है।


चूँकि हम आम तौर पर विभिन्न इनपुट लंबाई पर समय जटिलता की निर्भरता में रुचि रखते हैं, शब्दावली का दुरुपयोग करते हुए, समय जटिलता को कभी-कभी मैपिंग के रूप में संदर्भित किया जाता है <math>t_{\mathsf{A}} \colon \N \to \N</math>, अधिकतम जटिलता द्वारा परिभाषित
चूँकि हम सामान्यतः विभिन्न इनपुट लंबाई पर समय जटिलता की निर्भरता में रुचि रखते हैं, शब्दावली का दुरुपयोग करते हुए, समय जटिलता को कभी-कभी अधिकतम जटिलता द्वारा परिभाषित मैपिंग <math>t_{\mathsf{A}} \colon \N \to \N</math> के रूप में संदर्भित किया जाता है।
:<math>t_{\mathsf{A}}(n) := \max_{s\in \{0, 1\}^n} t_{\mathsf{A}}(s)</math>
:<math>t_{\mathsf{A}}(n) := \max_{s\in \{0, 1\}^n} t_{\mathsf{A}}(s)</math>  
इनपुट का <math>s</math> लंबाई या आकार के साथ <math>\le n</math>.
लंबाई या आकार <math>\le n</math> के साथ इनपुट <math>s</math> की।


[[अंतरिक्ष जटिलता]], यादृच्छिकता जटिलता आदि के लिए समान परिभाषाएँ दी जा सकती हैं।
[[अंतरिक्ष जटिलता]], यादृच्छिकता जटिलता आदि के लिए समान परिभाषाएँ दी जा सकती हैं।


==बोलने के तरीके==
==बोलने की विधि ==
बहुत बार, जटिलता <math>t_{\mathsf{A}}</math> एक एल्गोरिदम का <math>\mathsf{A}</math> एसिम्प्टोटिक [[बिग-ओ नोटेशन]] में दिया गया है, जो इसकी वृद्धि दर को फॉर्म में देता है <math>t_{\mathsf{A}} = O(g(n))</math> एक निश्चित वास्तविक मूल्यवान तुलना फ़ंक्शन के साथ <math>g(n)</math> और अर्थ:
बहुत बार, किसी एल्गोरिदम <math>\mathsf{A}</math> की जटिलता <math>t_{\mathsf{A}}</math> एसिम्प्टोटिक बिग-ओ नोटेशन में दी जाती है, जो इसकी वृद्धि दर को फ़ॉर्म में देती है।<math>t_{\mathsf{A}} = O(g(n))</math> एक निश्चित वास्तविक मूल्य तुलना फलन <math>g(n)</math> और अर्थ के साथ:
* एक सकारात्मक [[वास्तविक संख्या]] मौजूद है <math>M</math> और एक [[प्राकृतिक संख्या]] <math>n_0</math> ऐसा है कि
*एक सकारात्मक वास्तविक संख्या <math>M</math> और एक प्राकृतिक संख्या <math>n_0</math> उपस्थित है
:<math>|t_{\mathsf{A}}(n)| \le M g(n) \quad \text{ for all } n\ge n_0.</math>
:<math>|t_{\mathsf{A}}(n)| \le M g(n) \quad \text{ for all } n\ge n_0.</math>
अक्सर, शब्दांकन है:
अक्सर, शब्दांकन है:
* "कलन विधि <math>\mathsf{A}</math> सबसे खराब स्थिति वाली जटिलता है <math>O(g(n))</math>.“
*„एल्गोरिदम <math>\mathsf{A}</math>में सबसे खराब स्थिति वाली जटिलता <math>O(g(n))</math> है।
या यहां तक ​​कि केवल:
या यहां तक ​​कि केवल:
* "कलन विधि <math>\mathsf{A}</math> जटिलता है <math>O(g(n))</math>.
* "कलन विधि <math>\mathsf{A}</math> जटिलता <math>O(g(n))</math>.“है


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


== यह भी देखें ==
== यह भी देखें ==

Revision as of 09:48, 4 July 2023


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

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

किसी एल्गोरिदम की सबसे खराब स्थिति वाली जटिलता की तुलना उसकी औसत-केस जटिलता से की जानी चाहिए, जो कि यादृच्छिक इनपुट पर एल्गोरिदम द्वारा उपयोग किए जाने वाले संसाधनों की मात्रा का औसत माप है।

परिभाषा

गणना के एक मॉडल और एक एल्गोरिदम को देखते हुए जो प्रत्येक इनपुट पर रुकता है, मैपिंग को की समय जटिलता कहा जाता है, यदि प्रत्येक इनपुट स्ट्रिंग के लिए, } ठीक चरणों के बाद रुक जाता है।

चूँकि हम सामान्यतः विभिन्न इनपुट लंबाई पर समय जटिलता की निर्भरता में रुचि रखते हैं, शब्दावली का दुरुपयोग करते हुए, समय जटिलता को कभी-कभी अधिकतम जटिलता द्वारा परिभाषित मैपिंग के रूप में संदर्भित किया जाता है।

लंबाई या आकार के साथ इनपुट की।

अंतरिक्ष जटिलता, यादृच्छिकता जटिलता आदि के लिए समान परिभाषाएँ दी जा सकती हैं।

बोलने की विधि

बहुत बार, किसी एल्गोरिदम की जटिलता एसिम्प्टोटिक बिग-ओ नोटेशन में दी जाती है, जो इसकी वृद्धि दर को फ़ॉर्म में देती है। एक निश्चित वास्तविक मूल्य तुलना फलन और अर्थ के साथ:

  • एक सकारात्मक वास्तविक संख्या और एक प्राकृतिक संख्या उपस्थित है

अक्सर, शब्दांकन है:

  • „एल्गोरिदम में सबसे खराब स्थिति वाली जटिलता है।

या यहां तक ​​कि केवल:

  • "कलन विधि जटिलता .“है

उदाहरण

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

यह भी देखें

संदर्भ

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 2.2: Analyzing algorithms, pp.25-27.
  • Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. ISBN 0-521-88473-X, p.32.