क्या कोई बिग ओमेगा बनाम बिग थेटा बनाम बिग ओ समझा सकता है?

Question

संभव डुप्लिकेट:
Big Theta Notation - what exactly does big Theta represent?

मैं सिद्धांत रूप में यह समझते हैं, मुझे लगता है कि है, लेकिन क्या मैं मुसीबत लोभी हो रही तीन का अनुप्रयोग है।

स्कूल में, हम हमेशा एल्गोरिदम की जटिलता को दर्शाने के लिए बिग ओ का उपयोग करते थे। उदाहरण के लिए बबल सॉर्ट ओ (एन^2) था।

अब कुछ और सिद्धांत पढ़ने के बाद मुझे लगता है कि बिग ओह एकमात्र उपाय नहीं है, कम से कम दो अन्य दिलचस्प हैं।

बिग ओ ऊपरी बाध्य, बिग ओमेगा लोअर बाउंड है, और बड़ी थीटा दो का एक मिश्रण है:

लेकिन यहाँ मेरे सवाल है। लेकिन इसका क्या मतलब अवधारणा से है? मैं समझता हूं कि ग्राफ पर इसका क्या अर्थ है; मैंने इसके लाखों उदाहरण देखे हैं। लेकिन एल्गोरिदम जटिलता के लिए इसका क्या अर्थ है? इसके साथ "ऊपरी बाउंड" या "निचला बाध्य" मिश्रण कैसे होता है?

मुझे लगता है कि मुझे बस इसका आवेदन नहीं मिला है। मैं समझता हूं कि अगर कुछ स्थिर सी द्वारा गुणा किया जाता है कि यदि कुछ मान n_0 f (x) g (x) से अधिक है, तो f (x) ओ (जी (x)) माना जाता है। लेकिन इसका क्या मतलब व्यावहारिक रूप से है? हम कुछ मूल्य सी द्वारा एफ (एक्स) गुणा क्यों करेंगे? नरक, मैंने सोचा कि बिग ओ नोटेशन गुणक से कोई फर्क नहीं पड़ता।

Answer 1

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

अर्द्ध सहज परिभाषा इस प्रकार है:

एक समारोह g (x) हे होना कहा जाता है (f (x)) यदि "पर कुछ बिंदु से", g (x) ग से कम है * एफ (एक्स), जहां सी कुछ स्थिर है।

अन्य परिभाषाएं समान हैं, थीटा मांग कर रही है कि जी (एक्स) एफ (एक्स), ओमेगा मांगने वाले जी (एक्स)> सी * एफ (एक्स) के दो निरंतर गुणांक के बीच हो, और छोटे संस्करणों की मांग है कि यह है ऐसे सभी स्थिरांक के लिए सच है।

लेकिन यह कहना दिलचस्प क्यों है, उदाहरण के लिए, एक एल्गोरिदम ने ओ (एन^2) का समय चलाया है?

यह मुख्य रूप से दिलचस्प है क्योंकि सैद्धांतिक कंप्यूटर विज्ञान में, हम सबसे अधिक रुचि रखते हैं कि एल्गोरिदम बड़े इनपुट के लिए कैसे व्यवहार करते हैं। यह सच है क्योंकि छोटे इनपुट पर एल्गोरिदम रन टाइम कार्यान्वयन, संकलन, हार्डवेयर और ऐसी अन्य चीजों के आधार पर काफी भिन्न हो सकते हैं जो सैद्धांतिक रूप से एल्गोरिदम का विश्लेषण करते समय वास्तव में दिलचस्प नहीं होते हैं।

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

दूसरी तरफ, यदि आपके पास एक एल्गोरिदम है जो बिल्कुल 5 एन सेकेंड में चलता है, और दूसरा जो 1000n सेकेंड में चलता है (जो कि लंबे समय तक और एक = 3 के लिए लॉन्च ब्रेक के बीच अंतर है) उदाहरण के लिए, जब आप n = 1000000000000 पर जाते हैं, तो पैमाने में अंतर कम महत्वपूर्ण लगता है। यदि आपके पास एक एल्गोरिदम है जो O (लॉग n) लेता है, हालांकि, आपको लॉग (1000000000000) = 12 सेकंड का इंतजार करना होगा, शायद लगभग 317,0 9 8 वर्षों की बजाय कुछ स्थिरांक से गुणा करना होगा, इससे कोई फर्क नहीं पड़ता कि निरंतर कितना बड़ा है, एक पूरी तरह से अलग पैमाने है।

मुझे आशा है कि इससे चीजें थोड़ा स्पष्ट हो जाएंगी। तुम्हारी पढ़ाई के लिए शुभकामनाएं!