ओ (1) और Θ (1) के बीच क्या अंतर है?

Question

मैं उन दोनों की परिभाषा पता है, लेकिन क्या कारण कभी कभी मैं देख रहा हूँ है हे (1) और अन्य समय Θ (1) पाठ्यपुस्तकों में लिखा?

धन्यवाद।

Answer 1

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

Answer 2

ओ (1) और Θ (1) आवश्यक नहीं हैं यदि आप वास्तविक संख्याओं पर कार्यों के बारे में बात कर रहे हैं। उदाहरण के लिए, फ़ंक्शन f (n) = 1/n पर विचार करें। यह फ़ंक्शन ओ (1) है क्योंकि किसी भी n ≥ 1, f (n) ≤ 1. के लिए, यह Θ (1) निम्न कारणों से नहीं है: f (n) = Θ (g (n) की एक परिभाषा)) यह है कि | एफ (एन)/जी (एन) | की सीमा के रूप में एन अनंत को जाता है कुछ परिमित मान 0 < एल एफ में Plugging (एन) = 1/n और जी (एन) = 1 संतोषजनक एल है, हम की सीमा ले | 1/एन | क्योंकि एन अनंतता में जाता है और यह 0 है। इसलिए, एफ (एन) ≠ Θ (1)।

आशा है कि इससे मदद मिलती है!