रिकर्सन

Question

के साथ बिग ओ नोटेशन की गणना करना मैंने बिग ओ नोटेशन सबसे खराब केस रनटाइम को समझने का प्रयास किया है। लेकिन मुझे अभी भी यह समझ में नहीं आता है।

def g(n): 
    if n==0: 
     return 1 
    elif n==1: 
     return 2 
    else: 
     n_div=n//2 
     n_mod=n%2 
     return g(n_div)*g(n_mod) 

तो मुझे आशा है कि मैं कम से कम सही है कि कर रहा हूँ कि:

def g(n): 
    if n==0: 
     return 1 

और:

elif n==1: 
    return 2 

हैं हे

यह कुछ कोड है कि मैं हाल ही में लिखा है (1), इतना स्थिर।

लेकिन क्या else भाग के बारे में।

यह हे (एन) है क्योंकि यह n है कि मैं चयन पर निर्भर करता है?

किसी को भी व्याख्या कर सकते हैं क्या else भाग की है कि बिग ओ जटिलता है?

Answer 1

वैसे आप पाया है कि आपने 3 अलग-अलग मामलों में अपने समारोह अलग कर सकते हैं और पहले से ही पहचान है कि पहले 2 हैं हे (1)। तीसरा थोड़ा और मुश्किल है लेकिन आप इसे दो हिस्सों में भी अलग कर सकते हैं।

प्रत्यावर्तन स्पष्ट रूप से होता है से:

g(n//2)*g(n%2) 

हम तुरंत देख सकते हैं कि n%2 0 या 1 है, जो फिर से पहले 2 मामलों में से एक का समाधान हो जाएगा करने के लिए या तो मूल्यांकन करेंगे, तो हम है कि उपेक्षा कर सकते हैं। g(n//2) के साथ हमें छोड़कर। एक प्रिंटिंग पाश के रूप में इस फिर से लिखने और उत्पादन की जांच करके आप कुछ पर ध्यान देंगे:

>>> n = 37 
>>> while n > 1: 
...  n //= 2 
...  print(n) 
... 
18 
9 
4 
2 
1 

आप आधा हर बार द्वारा शर्तों कमी देख सकते हैं, और एक ही प्रत्यावर्तन में होता है। यह लॉगरिदमिक है।

नतीजतन इस कार्य के लिए सबसे खराब स्थिति ओ (logn) है।

आप क्या logn वास्तव में this question को देखकर बिग-ओ अंकन में मतलब है के बारे में अधिक सीख सकते हैं।

Answer 2

ओ नोटेशन वास्तव में कार्यक्रम के एक हिस्से के लिए नहीं है। यह वास्तव में उस तरीके को मापता है जिसमें इनपुट आकार बढ़ने के साथ चलने का समय बढ़ता है। इस मामले में, समय लेने वाला हिस्सा अंतिम भाग है।

आपको यह पता लगाना होगा कि यह आपके प्रोग्राम के लिए कैसे काम करता है। यहां एक सरल अनुभवजन्य विश्लेषण है जो आपकी मदद कर सकता है। यदि हम कार्यक्रम को कम से कम प्रिंट करने के लिए प्रोग्राम करते हैं तो अंतिम else भाग किसी दिए गए इनपुट के लिए कितनी बार चलता है, तो हमें यह मिलता है।

n | times 
-----+----- 
    2 | 1 
    4 | 2 
    8 | 3 
    16 | 4 
    32 | 5 
    64 | 6 
128 | 7 
256 | 8 
512 | 9 
1024 | 10 
2048 | 11 
4096 | 12 
8192 | 13 

यदि आप इसे प्लॉट करते हैं, तो आप ऐसा कुछ देखेंगे।

आपको लगता है कि इनपुट के आकार में वृद्धि, कॉल की संख्या भी बढ़ जाती है, लेकिन उप के रूप में रैखिक देख सकते हैं।वास्तव में, यह लॉगरिदमिक है क्योंकि आपके n लूप के प्रत्येक पुनरावृत्ति 50% से कम हो जाता है।