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

कंप्यूटर विज्ञान (विशेष रूप से कम्प्यूटेशनल जटिलता सिद्धांत) में, सबसे खराब स्थिति वाली जटिलता (इसे बिग-ओह (एन) द्वारा दर्शाया गया है) सिस्टम संसाधन (उदाहरण के लिए रनिंग टाइम, स्मृति ) को मापती है, जिसे एक कलन विधि को मनमाने आकार के इनपुट की आवश्यकता होती है ( सामान्यतः के रूप में दर्शाया जाता है 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)$

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

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

बोलने के तरीके

बहुत बार, जटिलता $t_{\mathsf {A}}$ एक एल्गोरिदम का ${\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})$.

यह भी देखें

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

संदर्भ

• 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.