big o - निचले बाध्य और तंग बाध्य के बीच अंतर?




big-o big-theta (5)

इस answer के संदर्भ में, थेटा (तंग बाध्य) क्या है?

ओमेगा कम बाध्य है, काफी समझा जाता है, कम से कम एक एल्गोरिदम ले सकता है। और हम जानते हैं कि बिग-ओ ऊपरी बाउंड के लिए है, इसका मतलब है कि एल्गोरिदम अधिकतम समय ले सकता है। लेकिन मुझे थेटा के बारे में कोई जानकारी नहीं है।


अगर मैं आलसी था, तो मैं कह सकता था कि एक क्रमबद्ध सरणी पर बाइनरी खोज ओ (एन 2), ओ (एन 3), और ओ (2 एन) है, और मैं हर मामले में तकनीकी रूप से सही होगा।

हम ऊपरी बाउंड को इंगित करने के लिए ओ-नोटेशन ("थोड़ा-ओह") का उपयोग कर सकते हैं जो असम्बद्ध रूप से तंग नहीं है। बड़े-ओह और छोटे-ओह दोनों समान हैं। लेकिन, बड़े-ओह की संभावना असम्बद्ध रूप से तंग ऊपरी सीमा को परिभाषित करने के लिए प्रयोग की जाती है।


के बीच बुनियादी अंतर

Blockquote

asymptotically ऊपरी बाध्य और asymptotically तंग Asym.upperbound का अर्थ है एक दिया algorythm जो इनपुट की संख्या के आधार पर अधिकतम मात्रा के साथ निष्पादित कर सकते हैं, उदाहरण के लिए अगर सभी सरणी (एन) तत्व अवरोही क्रम में हैं तो उन्हें आरोही करने के लिए ओ (एन) का एक चलने वाला समय लेगा जो ऊपरी बाध्य जटिलता दिखाता है, लेकिन यदि वे पहले से ही क्रमबद्ध हैं तो यह ओम (1) ले जाएगा। इसलिए हम आम तौर पर ऊपरी बाध्य जटिलता के लिए "ओ" नोटेशन का उपयोग करते हैं।

Asym। कसकर बाउंड उदाहरण के लिए दिखाता है (c1g (n) <= f (n) <= c2g (n)) तंग बाध्य सीमा दिखाता है जैसे कि फ़ंक्शन में दो बाउंड (ऊपरी बाउंड और निचले बाउंड) के बीच का मान होता है, जिससे औसत मामला


वाक्यांश न्यूनतम समय और अधिकतम समय यहां थोड़ा भ्रामक हैं। जब हम बड़े ओ नोटेशन के बारे में बात करते हैं, तो यह वास्तविक समय नहीं है जिसमें हम रुचि रखते हैं, इस प्रकार हमारे इनपुट आकार में बड़ा होने पर समय बढ़ता है। और आमतौर पर यह औसत या सबसे खराब मामला समय है जिसके बारे में हम बात कर रहे हैं, सबसे अच्छा मामला नहीं, जो आमतौर पर हमारी समस्याओं को हल करने में सार्थक नहीं है।

एक उदाहरण के रूप में दूसरे प्रश्न के स्वीकृत उत्तर में सरणी खोज का उपयोग करना। आकार एन की सूची में किसी विशेष संख्या को खोजने में लगने वाला समय औसत में n / 2 * some_constant होता है। यदि आप इसे फ़ंक्शन f(n) = n/2*some_constant , तो यह चार्ली द्वारा दिए गए अर्थ में g(n) = n से तेज नहीं g(n) = n । इसके अलावा, यह g(n) से भी धीमी गति से बढ़ता है। इसलिए, g(n) वास्तव में बिग-ओ नोटेशन में ऊपरी बाउंड और f(n) की निचली सीमा दोनों है, इसलिए रैखिक खोज की जटिलता बिल्कुल एन है , जिसका अर्थ है कि यह थेटा (एन) है।

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


Θ-नोटेशन (थेटा नोटेशन) को कड़े बाध्य कहा जाता है क्योंकि यह ओ-नोटेशन और Ω-नोटेशन (ओमेगा नोटेशन) से अधिक सटीक है।

अगर मैं आलसी था, तो मैं कह सकता था कि एक क्रमबद्ध सरणी पर बाइनरी खोज ओ (एन 2 ), ओ (एन 3 ), और ओ (2 एन ) है, और मैं हर मामले में तकनीकी रूप से सही होगा। ऐसा इसलिए है क्योंकि ओ-नोटेशन केवल ऊपरी बाउंड निर्दिष्ट करता है, और बाइनरी खोज उन सभी कार्यों द्वारा उच्च तरफ बाध्य होती है, बस बहुत बारीकी से नहीं। ये आलसी अनुमान बेकार होंगे

Θ-नोटेशन ओ-नोटेशन और Ω-नोटेशन को जोड़कर इस समस्या को हल करता है। अगर मैं कहता हूं कि बाइनरी खोज Θ (लॉग एन) है, जो आपको अधिक सटीक जानकारी देता है। यह आपको बताता है कि एल्गोरिदम दोनों पक्षों को दिए गए फ़ंक्शन द्वारा बाध्य किया गया है, इसलिए यह कभी भी उल्लेखनीय रूप से तेज़ या धीमा नहीं होगा।


Asymptotic ऊपरी बाउंड का मतलब है कि एक दिए गए एल्गोरिदम इनपुट की संख्या के आधार पर, अधिकतम मात्रा के दौरान निष्पादित करता है।

चलिए एक उदाहरण के रूप में एक सॉर्टिंग एल्गोरिदम लेते हैं। यदि किसी सरणी के सभी तत्व अवरोही क्रम में हैं, तो उन्हें सॉर्ट करने के लिए, इसमें O(n) का चलने वाला समय लगेगा, जो ऊपरी बाध्य जटिलता दिखा रहा है। यदि सरणी पहले से ही क्रमबद्ध है, तो मान O(1)

आम तौर पर, ऊपरी बाध्य जटिलता के लिए O-notation का उपयोग किया जाता है।

Asymptotically तंग बंधे (सी 1 जी (एन) ≤ एफ (एन) ≤ सी 2 जी (एन)) एक समारोह के लिए औसत बाध्य जटिलता दिखाता है, जिसमें सीमा सीमा (ऊपरी बाउंड और निचली बाध्य) के बीच एक मूल्य है, जहां सी 1 और सी 2 स्थिरांक हैं।