डेटा संरचनाएं - एसिम्प्टोटिक विश्लेषण

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

असममित विश्लेषण इनपुट बाध्य है अर्थात, यदि एल्गोरिथ्म के लिए कोई इनपुट नहीं है, तो यह एक निरंतर समय में काम करने के लिए संपन्न होता है। "इनपुट" के अलावा अन्य सभी कारकों को स्थिर माना जाता है।

असममित विश्लेषण का तात्पर्य संगणना की गणितीय इकाइयों में किसी भी संचालन के चलने के समय की गणना करना है। उदाहरण के लिए, एक ऑपरेशन के रनिंग समय की गणना f (n) के रूप में की जाती है और दूसरे ऑपरेशन के लिए हो सकती है जिसे g (n ² ) के रूप में गणना की जाती है । इसका मतलब है कि पहले ऑपरेशन के समय में वृद्धि के साथ रैखिक रूप से वृद्धि होगीn और दूसरे ऑपरेशन के चलने का समय तेजी से बढ़ेगा जब nबढ़ती है। इसी तरह, दोनों ऑपरेशंस का रनिंग टाइम लगभग एक जैसा होगाn काफी छोटा है।

आमतौर पर एक एल्गोरिथ्म के लिए आवश्यक समय तीन प्रकारों के अंतर्गत आता है -

Best Case - कार्यक्रम निष्पादन के लिए न्यूनतम समय की आवश्यकता।
Average Case - कार्यक्रम के निष्पादन के लिए औसत समय आवश्यक है।
Worst Case - कार्यक्रम के निष्पादन के लिए अधिकतम समय की आवश्यकता।

असममित संकेतन

एल्गोरिथ्म के चल रहे समय की जटिलता की गणना करने के लिए आमतौर पर उपयोग किए जाने वाले स्पर्शोन्मुख नोटेशन निम्नलिखित हैं।

Ο संकेतन
Ω संकेतन
θ संकेतन

बिग ओह संकेतन, Ο

नोटिफिकेशन express (n) एक एल्गोरिथ्म के चलने के समय की ऊपरी सीमा को व्यक्त करने का औपचारिक तरीका है। यह सबसे खराब स्थिति समय की जटिलता को मापता है या एक एल्गोरिथ्म को पूरा करने में संभवतः सबसे लंबा समय लगता है।

उदाहरण के लिए, एक फ़ंक्शन के लिए f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n₀ such that f(n) ≤ c.g(n) for all n > n₀. }

ओमेगा संकेतन, Ω

नोटिफिकेशन express (n) एक एल्गोरिथ्म के चलने के समय की निचली सीमा को व्यक्त करने का औपचारिक तरीका है। यह सबसे अच्छा मामला समय जटिलता मापता है या एक एल्गोरिथ्म संभवतः पूरा करने के लिए ले सकता है समय की सबसे अच्छी राशि।

उदाहरण के लिए, एक फ़ंक्शन के लिए f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

थीटा संकेतन, θ

नोटेशन express (n) एक एल्गोरिथ्म के रनिंग टाइम के निचले बाउंड और अपर बाउंड दोनों को व्यक्त करने का औपचारिक तरीका है। इसे निम्नानुसार दर्शाया गया है -

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n₀. }

आम विषमता संबंधी सूचनाएं

निम्नलिखित कुछ सामान्य स्पर्शोन्मुख सूचनाओं की एक सूची है -

स्थिर	-	Ο (1)
लघुगणक	-	N (लॉग एन)
रैखिक	-	Ο (एन)
n लॉग एन	-	N (एन लॉग एन)
द्विघात	-	² (एन ² )
घन	-	³ (एन ³ )
बहुपद	-	एन ^{1 (1)}
घातीय	-	2 ^{n (एन)}