algorithm
डायनामिक प्रोग्रामिंग के अनुप्रयोग

परिचय

टिप्पणियों

फाइबोनैचि संख्या

डायनेमिक प्रोग्रामिंग के लिए फाइबोनैचि संख्या एक प्रमुख विषय है क्योंकि पारंपरिक पुनरावर्ती दृष्टिकोण बहुत बार गणना करता है। इन उदाहरणों में मैं f(0) = f(1) = 1 के बेस केस का उपयोग करूंगा।

यहाँ एक उदाहरण है रिट्रिसिव ट्री fibonacci(4) , बार-बार गणना पर ध्यान दें:

गैर-गतिशील प्रोग्रामिंग O(2^n) रनटाइम जटिलता, O(n) स्टैक जटिलता

def fibonacci(n):
    if n < 2:
        return 1
    return fibonacci(n-1) + fibonacci(n-2)

समस्या लिखने का यह सबसे सहज तरीका है। जब तक आप बेस केस n < 2 हिट नहीं करते तब तक स्टैक स्पेस में O(n) हो जाएगा, जब आप पहली बार पुनरावर्ती शाखा कॉलिंग को fibonacci(n-1) ले जाएंगे।

O(2^n) रनटाइम जटिलता प्रमाण जो यहां देखा जा सकता है: फाइबोनैचि अनुक्रम की कम्प्यूटेशनल जटिलता । ध्यान देने की मुख्य बात यह है कि रनटाइम घातांक है, जिसका अर्थ है कि इसके लिए रनटाइम हर बाद के कार्यकाल के लिए दोगुना होगा, fibonacci(15) रूप में लंबे समय तक दोगुना होगा fibonacci(14) ।

मेमोइज्ड O(n) रनटाइम कॉम्प्लेक्सिटी, O(n) स्पेस जटिलता, O(n) स्टैक जटिलता

memo = []
memo.append(1) # f(1) = 1
memo.append(1) # f(2) = 1

def fibonacci(n):
    if len(memo) > n:
        return memo[n]

    result = fibonacci(n-1) + fibonacci(n-2)
    memo.append(result) # f(n) = f(n-1) + f(n-2)
    return result

संस्मरणात्मक दृष्टिकोण के साथ हम एक ऐसे ऐरे को पेश करते हैं जिसे पिछले सभी फंक्शन कॉल्स के रूप में सोचा जा सकता है। स्थान memo[n] फ़ंक्शन कॉल fibonacci(n) का परिणाम है। यह हमें O(n) रनटाइम के लिए O(n) अंतरिक्ष जटिलता का व्यापार करने की अनुमति देता है क्योंकि हमें डुप्लिकेट फ़ंक्शन कॉल की गणना करने की आवश्यकता नहीं है।

Iterative डायनामिक प्रोग्रामिंग O(n) रनटाइम जटिलता, O(n) स्पेस जटिलता, कोई पुनरावर्ती स्टैक

def fibonacci(n):
    memo = [1,1] # f(0) = 1, f(1) = 1

    for i in range(2, n+1):
         memo.append(memo[i-1] + memo[i-2])

    return memo[n]

यदि हम समस्या को इसके मूल तत्वों में तोड़ते हैं, तो आप देखेंगे कि फ़ोटोग्राफ़ी fibonacci(n) गणना करने के लिए हमें fibonacci(n-1) और fibonacci(n-2) । इसके अलावा, हम देख सकते हैं कि हमारा आधार मामला उस पुनरावर्ती पेड़ के अंत में दिखाई देगा जैसा कि ऊपर देखा गया है।

इस जानकारी के साथ, यह अब समाधान की ओर पीछे की गणना करने के लिए समझ में आता है, आधार मामलों पर शुरू होता है और ऊपर की ओर काम करता है। अब fibonacci(n) गणना करने के लिए, हम पहले n और n माध्यम से सभी रिट्रेसमेंट नंबर की गणना करते हैं।

यहाँ यह मुख्य लाभ यह है कि हमने अब O(n) रनटाइम रखते हुए पुनरावर्ती स्टैक को समाप्त कर दिया है। दुर्भाग्य से, हमारे पास अभी भी एक O(n) स्थान की जटिलता है लेकिन इसे भी बदला जा सकता है।

उन्नत Iterative डायनेमिक प्रोग्रामिंग O(n) रनटाइम जटिलता, O(1) स्पेस जटिलता, कोई पुनरावर्ती स्टैक

def fibonacci(n):
    memo = [1,1] # f(1) = 1, f(2) = 1

    for i in range (2, n):
        memo[i%2] = memo[0] + memo[1]

    return memo[n%2]

जैसा कि ऊपर उल्लेख किया गया है, पुनरावृत्त गतिशील प्रोग्रामिंग दृष्टिकोण आधार मामलों से शुरू होता है और अंतिम परिणाम तक काम करता है। O(1) (स्थिरांक) के लिए अंतरिक्ष जटिलता को प्राप्त करने के लिए बनाने के लिए महत्वपूर्ण अवलोकन वही अवलोकन है जिसे हमने पुनरावर्ती स्टैक के लिए बनाया है - हमें निर्माण करने के लिए केवल fibonacci(n-1) और fibonacci(n-2) है। fibonacci(n) । इसका मतलब यह है कि हमें केवल हमारे पुनरावृत्ति में किसी भी बिंदु पर fibonacci(n-1) और fibonacci(n-2) के परिणामों को बचाने की आवश्यकता है।

इन अंतिम 2 परिणामों को संग्रहीत करने के लिए, मैं आकार 2 की एक सरणी का उपयोग करता हूं और बस उस सूचकांक को फ्लिप करता हूं जिसे i % 2 का उपयोग करके असाइन कर रहा हूं जो कि वैकल्पिक होगा: 0, 1, 0, 1, 0, 1, ..., i % 2

मैं सरणी के दोनों अनुक्रमों को एक साथ जोड़ देता हूं क्योंकि हम जानते हैं कि जोड़ सराहनीय है ( 5 + 6 = 11 और 6 + 5 == 11 )। परिणाम फिर दो स्थानों ( i % 2 द्वारा चिह्नित) के पुराने को सौंपा गया है। अंतिम परिणाम तब स्थिति n%2 पर संग्रहीत किया जाता है

टिप्पणियाँ

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