विभिन्न फाइबोनैकी कार्यान्वयन के लिए बिग-ओ

Question

मैंने विभिन्न तरीकों से कोड (जावा में) को लागू करने का प्रयास किया जिसके द्वारा फाइबोनैकी अनुक्रम की nth अवधि की गणना की जा सकती है और मैं जो कुछ सीखा है उसे सत्यापित करने की उम्मीद कर रहा हूं।

public int memoizedFibonacci(int n) 
    { 
    if (n <= 0) return -1; 
    else if (n == 1) return 0; 
    else if (n == 2) return 1; 
    if (memory[n-1] == 0) 
     memory[n-1] = memoizedFibonacci(n-1); 
    if (memory[n-2] == 0) 
     memory[n-2] = memoizedFibonacci(n-2); 
    return memory[n-1]+memory[n-2]; 
    } 

मैं -:

public int recursiveFibonacci(int n) 
    { 
    if (n == 1) return 0; 
    else if (n == 2) return 1; 
    return recursiveFibonacci(n-1) + recursiveFibonacci(n-2); 
    } 

memoized कार्यान्वयन इस प्रकार है: -

public int iterativeFibonacci(int n) 
{ 
    if (n == 1) return 0; 
    else if (n == 2) return 1; 
    int i = 0, j = 1, sum = 0; 
    for (; (n-2) != 0; --n) 
    { 
    sum = i + j; 
    i = j; 
    j = sum; 
    } 
    return sum; 
} 

पुनरावर्ती कार्यान्वयन इस प्रकार है:

पुनरावृत्ति कार्यान्वयन इस प्रकार है इन कार्यान्वयन के बिग-ओ को समझने की कोशिश करते समय मुझे कुछ संदेह है। मेरा मानना ​​है कि ओ (एन) होने के लिए पुनरावृत्ति कार्यान्वयन के रूप में यह एन -2 बार के माध्यम से loops।

पुनरावर्ती कार्य में, मूल्यों को फिर से तैयार किया जाता है, इसलिए मुझे लगता है कि यह ओ (एन^2) है।

ज्ञापन समारोह में, आधे से अधिक मानों को ज्ञापन के आधार पर एक्सेस किया जाता है। मैंने पढ़ा है कि एक एल्गोरिदम ओ (लॉग एन) है यदि समस्या द्वारा समस्या स्थान को कम करने में लगातार समय लगता है और एक एल्गोरिदम ओ (एन) है यदि समस्या समस्या को कम करने में निरंतर समय लगता है निरंतर राशि। क्या मैं यह मानने में सही हूं कि ज्ञापन कार्यान्वयन जटिलता में ओ (एन) है? यदि हां, तो क्या पुनरावृत्ति कार्यान्वयन तीनों में सबसे अच्छा नहीं होगा? (क्योंकि यह अतिरिक्त स्मृति का उपयोग नहीं करता है जो ज्ञापन की आवश्यकता है)।

Answer 1

पुनरावर्ती संस्करण बहुपद समय नहीं है - यह घातीय, tightly bounded at φⁿ है जहां φ सुनहरा अनुपात (≈ 1.618034) है। रिकर्सिव संस्करण ओ (एन) मेमोरी (उपयोग स्टैक से आता है) का उपयोग करेगा।

Memoization संस्करण, पहली बार चलाने पर हे (n) समय लेने के बाद से प्रत्येक संख्या केवल एक बार की जाती है जाएगा। हालांकि, बदले में, यह ओ (n) आपके वर्तमान कार्यान्वयन के लिए स्मृति (n गणना मूल्य को संग्रहीत करने से पहले और पहले रन पर स्टैक के लिए भी आता है)। आप इसे कई बार चलाते हैं, समय जटिलता हो जाएगा हे (एम + क्ष) जहां एम सभी इनपुट n और क्ष का अधिकतम है प्रश्नों की संख्या है। स्मृति जटिलता ओ (एम) बन जाएगी, जो कि सभी गणना मूल्यों वाले सरणी से आता है।

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

(हालांकि, व्यावहारिक रूप से बोलते हुए, प्रदर्शन और स्मृति की समस्या से काफी पहले, यह संख्या 64-बिट पूर्णांक तक भी बहती है, इसलिए एक सटीक विश्लेषण को ध्यान में रखना चाहिए जब आप कंप्यूटिंग कर रहे हों पूर्ण संख्या)।

plesiv उल्लेख किया है, फाइबोनैचि संख्या भी हे में की जा सकती (लॉग n) आव्यूह गुणन से (हर कदम पर प्रतिपादक को आधा करने से एक ही चाल के रूप में तेजी से घातांक का उपयोग)।