algorithm
एल्गोरिथ्म जटिलता
खोज…
टिप्पणियों
सभी एल्गोरिदम एक समस्या को हल करने के लिए चरणों की एक सूची है। प्रत्येक चरण में पिछले चरणों के कुछ सेट पर निर्भरता है, या एल्गोरिथ्म की शुरुआत है। एक छोटी समस्या निम्नलिखित की तरह दिख सकती है:
इस संरचना को निर्देशित एसाइक्लिक ग्राफ या लघु के लिए डीएजी कहा जाता है। ग्राफ़ में प्रत्येक नोड के बीच के लिंक परिचालन के क्रम में निर्भरता का प्रतिनिधित्व करते हैं, और ग्राफ़ में कोई चक्र नहीं हैं।
निर्भरता कैसे होती है? उदाहरण के लिए निम्न कोड लें:
total = 0
for(i = 1; i < 10; i++)
total = total + i
इस psuedocode में, लूप के लिए प्रत्येक पुनरावृत्ति पिछले पुनरावृत्ति से परिणाम पर निर्भर करता है क्योंकि हम इस अगली पुनरावृत्ति में पिछले पुनरावृत्ति में गणना की गई मान का उपयोग कर रहे हैं। इस कोड के लिए DAG इस तरह दिख सकता है:
यदि आप एल्गोरिदम के इस प्रतिनिधित्व को समझते हैं, तो आप इसका उपयोग कार्य और अवधि के संदर्भ में एल्गोरिथ्म की जटिलता को समझने के लिए कर सकते हैं।
काम
कार्य संचालन की वास्तविक संख्या है जिसे दिए गए इनपुट आकार n लिए एल्गोरिथ्म के लक्ष्य को प्राप्त करने के लिए निष्पादित करने की आवश्यकता है।
स्पैन
स्पैन को कभी-कभी महत्वपूर्ण पथ के रूप में संदर्भित किया जाता है, और एल्गोरिथ्म के लक्ष्य को प्राप्त करने के लिए एक एल्गोरिथ्म में सबसे कम चरणों की आवश्यकता होती है।
निम्नलिखित छवि हमारे नमूना डीएजी पर काम और अवधि के बीच के अंतर को दिखाने के लिए ग्राफ पर प्रकाश डालती है।
काम एक पूरे के रूप में ग्राफ में नोड्स की संख्या है। यह ऊपर बाईं ओर ग्राफ द्वारा दर्शाया गया है। स्पैन महत्वपूर्ण पथ है, या शुरू से अंत तक सबसे लंबा रास्ता है। जब काम समानांतर में किया जा सकता है, तो सही प्रतिनिधित्व अवधि पर पीले हाइलाइट किए गए नोड्स, आवश्यक चरणों की सबसे कम संख्या। जब काम को सीरियसली किया जाना चाहिए, तो स्पैन काम की तरह ही होता है।
विश्लेषण के संदर्भ में काम और अवधि दोनों का स्वतंत्र रूप से मूल्यांकन किया जा सकता है। एल्गोरिथ्म की गति स्पैन द्वारा निर्धारित की जाती है। आवश्यक कम्प्यूटेशनल शक्ति की मात्रा कार्य द्वारा निर्धारित की जाती है।
बिग-थीटा संकेतन
बिग-ओ संकेतन के विपरीत, जो कुछ एल्गोरिथ्म के लिए चल रहे समय के केवल ऊपरी सीमा का प्रतिनिधित्व करता है, बिग-थीटा एक तंग बाध्य है; ऊपरी और निचले दोनों ही बाउंड। तंग बाउंड अधिक सटीक है, लेकिन गणना करने के लिए भी अधिक कठिन है।
बिग-थीटा संकेतन सममित है: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))
इसे समझने का एक सहज तरीका यह है कि f(x) = Ө(g(x)) अर्थ है कि f (x) और g (x) के ग्राफ एक ही दर से बढ़ते हैं, या यह कि रेखांकन बड़े के लिए समान व्यवहार करता है x के पर्याप्त मूल्य।
बिग-थीटा संकेतन की पूर्ण गणितीय अभिव्यक्ति इस प्रकार है:
) (F (x)) = {g: N 0 -> R और c 1 , c 2 , n 0 > 0, जहाँ c 1 <abs (g (n) / f (n)), हर n> n के लिए 0 और abs निरपेक्ष मान है}
एक उदाहरण
यदि इनपुट n लिए एल्गोरिथ्म को समाप्त करने में 42n^2 + 25n + 4 संचालन होता है, तो हम कहते हैं कि O(n^2) , लेकिन O(n^3) और O(n^100) । हालाँकि, यह, Ө(n^2) और यह Ө(n^3) , Ө(n^4) आदि नहीं है। एल्गोरिथम यानी कि Ө(f(n)) भी O(f(n)) , लेकिन इसके विपरीत नहीं!
औपचारिक गणितीय परिभाषा
Ө(g(x)) कार्यों का एक समूह है।
Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N}
क्योंकि Ө(g(x)) एक सेट है, हम यह संकेत करने के लिए f(x) ∈ Ө(g(x)) लिख सकते हैं कि f(x) Ө(g(x)) का सदस्य है। इसके बजाय, हम समान धारणा को व्यक्त करने के लिए आमतौर पर f(x) = Ө(g(x)) - यह सामान्य तरीका है।
जब भी Ө(g(x)) एक सूत्र में दिखाई देता है, हम इसे कुछ अनाम फ़ंक्शन के लिए खड़े होने के रूप में व्याख्या करते हैं जिन्हें हम नाम देने की परवाह नहीं करते हैं। उदाहरण के लिए समीकरण T(n) = T(n/2) + Ө(n) , जिसका अर्थ T(n) = T(n/2) + f(n) जहां f(n) सेट में एक समारोह है Ө(n) ।
बता दें कि वास्तविक संख्याओं के कुछ सबसेट पर f और g दो कार्य हैं। हम f(x) = Ө(g(x)) को x->infinity रूप में f(x) = Ө(g(x)) यदि और केवल तभी सकारात्मक स्थिरांक K और L और एक वास्तविक संख्या x0 जो धारण करता है:
K|g(x)| <= f(x) <= L|g(x)| सभी x >= x0 ।
परिभाषा इसके बराबर है:
f(x) = O(g(x)) and f(x) = Ω(g(x))
एक विधि जो सीमा का उपयोग करती है
यदि limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) अर्थात सीमा मौजूद है और यह सकारात्मक है, तो f(x) = Ө(g(x))
सामान्य जटिलता कक्षाएं
| नाम | नोटेशन | n = 10 | n = 100 |
|---|---|---|---|
| लगातार | Ө (1) | 1 | 1 |
| लघुगणक | Ө (लॉग (एन)) | 3 | 7 |
| रैखिक | Ө (एन) | 10 | 100 |
| Linearithmic | Ө (एन * लॉग (एन)) | 30 | 700 |
| द्विघात | Ө (एन ^ 2) | 100 | 10 000 |
| घातीय | Ө (2 ^ n) | १ ०२४ | 1.267650e + 30 |
| कारख़ाने का | Ө (एन!) | 3 628 800 | 9.332622e + 157 |
बिग-ओमेगा संकेतन
Ym-संकेतन का उपयोग असममित निचले बंध के लिए किया जाता है।
औपचारिक परिभाषा
बता दें कि f(n) और g(n) सकारात्मक वास्तविक संख्याओं के सेट पर दो कार्य हैं। हम लिखते हैं f(n) = Ω(g(n)) यदि सकारात्मक स्थिरांक हैं c और n0 ऐसे:
0 ≤ cg(n) ≤ f(n) for all n ≥ n0 ।
टिप्पणियाँ
f(n) = Ω(g(n)) अर्थ है कि f(n) असमान रूप से बढ़ता है g(n) की तुलना में धीमा नहीं है। इसके अलावा हम Ω(g(n)) बारे में कह सकते हैं जब एल्गोरिथ्म विश्लेषण Θ(g(n)) या / और O(g(n)) बारे में कथन के लिए पर्याप्त नहीं है।
प्रमेय की परिभाषा से प्रमेय निम्नानुसार है:
दो किसी भी कार्य के लिए f(n) और g(n) हमारे पास f(n) = Ө(g(n)) है और यदि केवल f(n) = O(g(n)) and f(n) = Ω(g(n)) ।
रेखांकन:-संकेतन का प्रतिनिधित्व निम्नानुसार किया जा सकता है:
उदाहरण के लिए, हमारे पास f(n) = 3n^2 + 5n - 4 । तब f(n) = Ω(n^2) । यह सही f(n) = Ω(n) , या f(n) = Ω(1) ।
परफेक्ट मैचिंग एल्गोरिथ्म को हल करने के लिए एक और उदाहरण: यदि कोने की संख्या विषम है, तो आउटपुट "नो परफेक्ट मैचिंग" अन्यथा सभी संभव मिलान का प्रयास करें।
हम कहने के लिए एल्गोरिथ्म घातीय समय की आवश्यकता है लेकिन वास्तव में आप एक साबित नहीं कर सकते चाहते हैं Ω(n^2) कम की सामान्य परिभाषा का उपयोग बाध्य Ω के लिए n विषम रैखिक समय में एल्गोरिथ्म रन के बाद से। इसके बजाय हमें असीम रूप से कई n लिए कुछ स्थिर c>0 , f(n)≥ cg(n) लिए कहकर f(n)=Ω(g(n)) को परिभाषित करना चाहिए। यह ऊपरी और निचले सीमा के बीच एक अच्छा पत्राचार देता है: f(n)=Ω(g(n)) iff f(n) != o(g(n)) ।
संदर्भ
औपचारिक परिभाषा और प्रमेय पुस्तक "थॉमस एच। कॉर्मेन, चार्ल्स ई। लिसेरसन, रोनाल्ड एल। रिवेस्ट, क्लिफोर्ड स्टीन से लिया गया है। परिचय के लिए एल्गोरिदम"।
स्पर्शोन्मुख संकेतन की तुलना
बता दें कि f(n) और g(n) पॉजिटिव रियल नंबर के सेट पर परिभाषित दो फंक्शन हैं, c, c1, c2, n0 पॉजिटिव रियल c, c1, c2, n0 हैं।
| नोटेशन | f (n) = O (g (n)) | f (n) = Ω (g (n)) | f (n) = Θ (g (n)) | f (n) = o (g (n)) | f (n) = ω (g (n)) |
|---|---|---|---|---|---|
| औपचारिक परिभाषा | ∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ cg(n) | ∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) ≤ f(n) | ∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) | ∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < cg(n) | ∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) < f(n) |
f, g और वास्तविक संख्याओं की एसिम्प्टोटिक तुलना के बीच सादृश्य a, b | a ≤ b | a ≥ b | a = b | a < b | a > b |
| उदाहरण | 7n + 10 = O(n^2 + n - 9) | n^3 - 34 = Ω(10n^2 - 7n + 1) | 1/2 n^2 - 7n = Θ(n^2) | 5n^2 = o(n^3) | 7n^2 = ω(n) |
| ग्राफिक व्याख्या |  | |  |
स्पर्शोन्मुख संकेतन को वेन आरेख पर निम्नानुसार दर्शाया जा सकता है: 
लिंक
थॉमस एच। कोरमेन, चार्ल्स ई। लिसेरसन, रोनाल्ड एल। रिवेस्ट, क्लिफोर्ड स्टीन। एल्गोरिदम का परिचय।