big o - Θ(एन) और ओ(एन) के बीच क्या अंतर है?




big-o time-complexity (6)

निष्कर्ष: हम बड़े ओ, बड़े θ और बड़े Ω को एक ही चीज़ के रूप में देखते हैं।

क्यूं कर? मैं नीचे कारण बताऊंगा:

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

बड़े ओ और बड़े θ के बीच स्पष्ट रूप से संबंधों को स्पष्ट करने के लिए, मैं पहले बड़े ओ और छोटे ओ के बीच संबंधों को समझाऊंगा। परिभाषा से, हम आसानी से जान सकते हैं कि छोटा ओ बड़ा ओ का सबसेट है। उदाहरण के लिए:

टी (एन) = एन ^ 2 + एन, हम टी (एन) = ओ (एन ^ 2), टी (एन) = ओ (एन ^ 3), टी (एन) = ओ (एन ^ 4) कह सकते हैं। लेकिन छोटे ओ के लिए, टी (एन) = ओ (एन ^ 2) छोटे ओ की परिभाषा को पूरा नहीं करता है। तो बस टी (एन) = ओ (एन ^ 3), टी (एन) = ओ (एन ^ 4) छोटे ओ के लिए सही हैं। अनावश्यक टी (एन) = ओ (एन ^ 2) क्या है? यह बड़ा θ है!

आम तौर पर, हम कहते हैं कि बड़ा ओ ओ ओ (एन ^ 2) है, शायद टी (एन) = ओ (एन ^ 3), टी (एन) = ओ (एन ^ 4) कहने के लिए। क्यूं कर? क्योंकि हम बड़े ओ को अवचेतन रूप से बड़े θ के रूप में देखते हैं।

इसी तरह, हम बड़े θ अवचेतन रूप से बड़े θ के रूप में भी देखते हैं।

एक शब्द में, बड़े ओ, बड़े θ और बड़े Ω परिभाषाओं से एक ही बात नहीं हैं, लेकिन वे हमारे मुंह और मस्तिष्क में एक ही बात हैं।

कभी-कभी मैं Θ (एन) को अजीब Θ प्रतीक के बीच में कुछ के साथ देखता हूं, और कभी-कभी केवल ओ (एन)। क्या यह सिर्फ टाइपिंग की आलस्य है क्योंकि कोई भी इस प्रतीक को टाइप करने के बारे में नहीं जानता है, या इसका मतलब कुछ अलग है?


सीमा का उपयोग करना

आइए सभी n लिए f(n) > 0 और g(n) > 0 । इस पर विचार करना ठीक है, क्योंकि सबसे तेज़ वास्तविक एल्गोरिदम में कम से कम एक ऑपरेशन होता है और शुरुआत के बाद इसके निष्पादन को पूरा करता है। यह कैलकुंस को सरल बना देगा, क्योंकि हम पूर्ण मूल्य ( |f(n)| ) के बजाय मान ( f(n) ) का उपयोग कर सकते हैं।

  1. f(n) = O(g(n))

    सामान्य:

              f(n)     
    0 ≤ lim ──────── < ∞
        n➜∞   g(n)
    

    g(n) = n :

              f(n)     
    0 ≤ lim ──────── < ∞
        n➜∞    n
    

    उदाहरण:

        Expression               Value of the limit
    ------------------------------------------------
    n        = O(n)                      1
    1/2*n    = O(n)                     1/2
    2*n      = O(n)                      2
    n+log(n) = O(n)                      1
    n        = O(n*log(n))               0
    n        = O(n²)                     0
    n        = O(nⁿ)                     0
    

    जवाबी उदाहरण:

        Expression                Value of the limit
    -------------------------------------------------
    n        ≠ O(log(n))                 ∞
    1/2*n    ≠ O(sqrt(n))                ∞
    2*n      ≠ O(1)                      ∞
    n+log(n) ≠ O(log(n))                 ∞
    
  2. f(n) = Θ(g(n))

    सामान्य:

              f(n)     
    0 < lim ──────── < ∞
        n➜∞   g(n)
    

    g(n) = n :

              f(n)     
    0 < lim ──────── < ∞
        n➜∞    n
    

    उदाहरण:

        Expression               Value of the limit
    ------------------------------------------------
    n        = Θ(n)                      1
    1/2*n    = Θ(n)                     1/2
    2*n      = Θ(n)                      2
    n+log(n) = Θ(n)                      1
    

    जवाबी उदाहरण:

        Expression                Value of the limit
    -------------------------------------------------
    n        ≠ Θ(log(n))                 ∞
    1/2*n    ≠ Θ(sqrt(n))                ∞
    2*n      ≠ Θ(1)                      ∞
    n+log(n) ≠ Θ(log(n))                 ∞
    n        ≠ Θ(n*log(n))               0
    n        ≠ Θ(n²)                     0
    n        ≠ Θ(nⁿ)                     0
    

एक chart पिछले उत्तरों को समझने में आसान बना सकता है:

Θ-नोटेशन - वही आदेश | ओ-नोटेशन - ऊपरी बाउंड

अंग्रेजी में,

बाईं तरफ, ध्यान दें कि ऊपरी बाउंड और निचली बाध्य है जो परिमाण के समान क्रम दोनों (यानी g(n) ) हैं। स्थिरांक को अनदेखा करें, और यदि ऊपरी बाउंड और निचले बाउंड में परिमाण का एक ही क्रम होता है, तो कोई वैध रूप से कह सकता है कि g(n) f(n) का Theta है।

दाएं से शुरू करना, सरल उदाहरण, यह कह रहा है कि f(n) का ऊपरी बाउंड (यानी big O ) g(n) । ध्यान दें कि g(n) केवल परिमाण का क्रम है और निरंतर c अनदेखा करता है (जैसा कि सभी big O नोटेशन करता है)।


एक बड़ा "ओ" है

एक बिग थेटा है

http://en.wikipedia.org/wiki/Big_O_notation

बिग ओ का मतलब है कि आपका एल्गोरिदम दिया गया अभिव्यक्ति (एन ^ 2) की तुलना में और अधिक चरणों में निष्पादित नहीं करेगा

बिग ओमेगा का मतलब है कि आपका एल्गोरिदम दिए गए अभिव्यक्ति की तुलना में कम चरणों में निष्पादित करेगा (एन ^ 2)

जब दोनों स्थितियां एक ही अभिव्यक्ति के लिए सच होती हैं, तो आप बड़े थेटा नोटेशन का उपयोग कर सकते हैं ....


याद रखने का एक आसान तरीका है (एक चाल, मुझे लगता है) जो नोटेशन का मतलब है।

सभी बिग-ओ नोटेशन को एक बार माना जा सकता है।

एक looking को देखते समय, बार नीचे है, इसलिए यह एक (एसिम्प्टोटिक) निचली बाध्य है।

एक looking को देखते समय, बार स्पष्ट रूप से बीच में होता है। तो यह एक (asymptotic) तंग बाध्य है।

जब हस्तलेखन ओ, आप आम तौर पर शीर्ष पर खत्म होते हैं, और एक झुकाव खींचते हैं। इसलिए ओ (एन) समारोह की ऊपरी सीमा है। निष्पक्ष होने के लिए, यह अधिकांश फोंट के साथ काम नहीं करता है, लेकिन यह नामों का मूल औचित्य है।


Big-O = afunction और Omega = afunction अनुलग्नक कहने के शॉर्टकट तरीके के रूप में Theta = afunction कहने के बारे में सोचें

जब समारोह के बड़े ओ और समारोह के ओमेगा समान होते हैं, तो थेटा उस विशेष स्थिति को संदर्भित करने का एक लघुरूप तरीका है।

इस प्रकार, यदि आप Theta = some expression कहते हैं, तो O = some expression , और Omega = some expression कहने के लिए अभी भी सही है। केवल अंतर यह है कि Theta = some expression में अधिक जानकारी होती है।

असहज समानता:

हे कहता है "उस जानवर के पास 5 पैरों से कम या बराबर है।" ओमेगा का कहना है, "उस जानवर के पास 5 से अधिक या बराबर है।"

थेटा कहने की तरह है कि "जानवर के पास 5 पैर हैं"।

दूसरे शब्दों में, यदि किसी जानवर के पास 5 पैर (थेटा) हैं, तो निम्नलिखित दोनों कथन सत्य हैं:

  1. जानवर के पास 5 या कम पैर हैं। (ओ)
  2. जानवर के पास 5 या अधिक पैर हैं। (ओमेगा)

बस ध्यान रखें, अभिव्यक्ति आवश्यक रूप से विशिष्ट संख्या नहीं हैं, लेकिन परिमाण के विभिन्न आदेशों के कार्य (लॉग (एन), एन, एन ^ 2, आदि)।