रिकर्सिव विधियों के बिग ओ

Question

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

धन्यवाद।

Answer 1

आप ऑर्डर को फिर से परिभाषित कर सकते हैं। उदाहरण के लिए, मान लें कि आपके पास एक फ़ंक्शन है f। एफ (एन) की गणना करने के लिए के कदम लेता है। अब आप एफ (एन + 1) की गणना करना चाहते हैं। आइए कहें कि f (n + 1) एक बार f (n) कॉल करता है, फिर f (n + 1) k + कुछ स्थिर चरणों को लेता है। प्रत्येक आमंत्रण कुछ स्थिर कदम उठाएगा, इसलिए यह विधि ओ (एन) है।

अब एक और उदाहरण देखें। कहते हैं कि तुम दो पिछले परिणामों को जोड़कर भोलेपन से फिबोनैकी को लागू कर सकते हैं:

fib(n) = { return fib(n-1) + fib(n-2) } 

अब कहते हैं कि तुम झूठ बोलना गणना कर सकते हैं देता है (n-2) और मिथ्या (n-1) दोनों कश्मीर कदम के बारे में में। फाइब (एन) की गणना करने के लिए आपको के + के = 2 * के चरणों की आवश्यकता है। अब कहें कि आप फिब (एन + 1) की गणना करना चाहते हैं। तो आपको fib (n-1) के लिए दो गुना अधिक कदमों की आवश्यकता है। तो ऐसा लगता है कि ओ (2^एन)

मान्य है, यह बहुत औपचारिक नहीं है, लेकिन उम्मीद है कि इस तरह से आप थोड़ा महसूस कर सकते हैं।

Answer 2

आप रिकर्सिव विधियों के बड़े ओ को खोजने के लिए मास्टर प्रमेय को संदर्भित करना चाहेंगे। यहां विकिपीडिया आलेख है: http://en.wikipedia.org/wiki/Master_theorem

आप पेड़ की तरह एक पुनरावर्ती समस्या के बारे में सोचना चाहते हैं। फिर, पेड़ के प्रत्येक स्तर और आवश्यक काम की मात्रा पर विचार करें। समस्याएं आम तौर पर 3 श्रेणियों में गिरती हैं, जड़ भारी (पहली पुनरावृत्ति >> पेड़ के बाकी), संतुलित (प्रत्येक स्तर में समान मात्रा में काम होता है), पत्ता भारी (अंतिम पुनरावृत्ति >> पेड़ के बाकी)। एक उदाहरण के रूप

लेने मर्ज प्रकार:

define mergeSort(list toSort): 
    if(length of toSort <= 1): 
     return toSort 
    list left = toSort from [0, length of toSort/2) 
    list right = toSort from [length of toSort/2, length of toSort) 
    merge(mergeSort(left), mergeSort(right)) 

आपको लगता है कि बदले में mergeSort की प्रत्येक कॉल 1/2 मूल लंबाई के 2 अधिक mergeSorts कॉल देख सकते हैं। हम जानते हैं कि विलय प्रक्रिया में विलय किए जाने वाले मूल्यों की संख्या के अनुपात में आनुपातिक समय लगेगा।

पुनरावृत्ति संबंध तब टी (एन) = 2 * टी (एन/2) + ओ (एन) है। दोनों 2 कॉल से आते हैं और एन/2 प्रत्येक कॉल से होता है जिसमें तत्वों की केवल आधा संख्या होती है। हालांकि, प्रत्येक स्तर पर तत्वों की संख्या समान होती है जिसे विलय करने की आवश्यकता होती है, इसलिए प्रत्येक स्तर पर निरंतर कार्य ओ (एन) होता है।

हम जानते हैं कि काम समान रूप से वितरित किया जाता है (ओ (एन) प्रत्येक गहराई) और पेड़ log_2 (n) गहरा है, इसलिए रिकर्सिव फ़ंक्शन का बड़ा ओ ओ (एन * लॉग (एन)) है।