सबसे खराब स्थिति जटिलता

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

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

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

परिभाषा

गणना के एक मॉडल और एक एल्गोरिदम ${\mathsf {A}}$ को देखते हुए जो प्रत्येक इनपुट $s$ पर रुकता है, मैपिंग $t_{\mathsf {A}}\colon \{0,1\}^{\star }\to \mathbb {N}$ को ${\mathsf {A}}$की समय जटिलता कहा जाता है, यदि प्रत्येक इनपुट स्ट्रिंग $s$ के लिए, ${\mathsf {A}}$} ठीक $t_{\mathsf {A}}(s)$ चरणों के बाद रुक जाता है।

चूँकि हम सामान्यतः विभिन्न इनपुट लंबाई पर समय जटिलता की निर्भरता में रुचि रखते हैं, शब्दावली का दुरुपयोग करते हुए, समय जटिलता को कभी-कभी अधिकतम जटिलता द्वारा परिभाषित मैपिंग $t_{\mathsf {A}}\colon \mathbb {N} \to \mathbb {N}$ के रूप में संदर्भित किया जाता है।

$t_{\mathsf {A}}(n):=\max _{s\in \{0,1\}^{n}}t_{\mathsf {A}}(s)$

लंबाई या आकार $\leq n$ के साथ इनपुट $s$ की।

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

बोलने की विधि

बहुत बार, किसी एल्गोरिदम ${\mathsf {A}}$ की जटिलता $t_{\mathsf {A}}$ एसिम्प्टोटिक बिग-ओ नोटेशन में दी जाती है, जो इसकी वृद्धि दर को फ़ॉर्म में देती है।$t_{\mathsf {A}}=O(g(n))$ एक निश्चित वास्तविक मूल्य तुलना फलन $g(n)$ और अर्थ के साथ:

• एक सकारात्मक वास्तविक संख्या $M$ और एक प्राकृतिक संख्या $n_{0}$ उपस्थित है

$|t_{\mathsf {A}}(n)|\leq Mg(n)\quad {\text{ for all }}n\geq n_{0}.$

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

• „एल्गोरिदम ${\mathsf {A}}$में सबसे खराब स्थिति वाली जटिलता $O(g(n))$ है।

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

• "कलन विधि ${\mathsf {A}}$ जटिलता $O(g(n))$.“है

उदाहरण

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

करें। एल्गोरिथम के लिए सबसे अच्छा स्थिति तब होता है जब संख्याएं पहले से ही क्रमबद्ध होती हैं, जो कार्य करने के लिए $O(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.