如何確定包含優化的遞歸算法的大O？

我知道Fibonacci算法的規則遞歸函數是O（2^n），因爲它爲每個後續調用調用自己兩次，使其成本加倍。但是，在添加我所描述的優化（對序列的解決方案哈希表）之後，如何確定它有多少可以降低複雜性？如何確定包含優化的遞歸算法的大O？

例如：

import java.util.*; 

public class Solution { 

    static Hashtable<Integer, Integer> numbers = new Hashtable<Integer, Integer>(); 

    public static int fibonacci(int n) { 
     if(n == 0 || n == 1){ 
      return n; 
     }else if(numbers.containsKey(n)){ 
      return numbers.get(n); 
     }else { 
      int result = fibonacci(n-1) + fibonacci(n-2); 
      numbers.put(n, result); 
      return result; 
     } 
    } 

    public static void main(String[] args) { 
     Scanner scanner = new Scanner(System.in); 
     int n = scanner.nextInt(); 
     scanner.close(); 
     System.out.println(fibonacci(n)); 
    } 
}

來源

2017-10-17 Remixt

1.「我知道斐波納契算法的正則遞歸函數是O（n^2）」 - 不是，它是O（2^n）。 2.你永遠不會填充'數字'。 3.一旦你實現了一個真正的記憶，你將只計算一次每個數字，所以'n'的運行時間將是O（n） – alfasin

我犯了一個錯誤，對不起 – Remixt

它也不是2^n，但phi^n，其中phi =（sqrt（5）+1）/ 2 = 1.618 ...是黃金比例。斐波納契（30）需要大約200萬步來計算天真，而不是10億。（從技術上講，它是O（2^n），但只是在同樣的意義上，它是O（2^2^n）：大O是一個上界。） – Charles

你的算法是O（n）。你已經實施的是所謂的memoization。這意味着當兩個（或一般多個）子問題部分重疊時（例如F(5) = F(4) + F(3)）突破問題時，兩者將需要計算F（2）以使它們重疊），當計算一個值時，它將被存儲，以便下一步所需時間已經計算完畢。

這意味着，爲了計算你會遞歸計算所有F(i) ,i<n如果某些F(i)是不止一次需要的時候將被計算一次，並且會在O(1)可用（由於Ø哈希表）。所以總體會O(n)。

這與動態算法版本非常相似（不同之處在於，您不需要構建解決方案，例如F（0），F（1），F（2）... F（n）跟蹤你的計算（記憶））。雖然我沒有檢查過你是否記憶算法有任何bug ...只是解釋memoization算法的概念和複雜性。

來源

2017-10-17 18:43:05 coder

正如評論指出的那樣，這個功能的複雜性是西塔（2^N）：

Fibonacci(n) { 
    if (n < 0) return 0; 
    if (n < 2) return 1; 
    return Fibonacci(n - 1) + Fibonacci(n - 2); 
}

我們可以通過歸納證明這一點。基本情況：對於n = 0和n = 1,0.5 * 2^n <= Fibonacci(n) = 1 <= 2 * 2^n。歸納假設：假設這適用於n直至幷包括k。感應步驟：顯示0.5 * 2^(k+1) <= Fibonacci(k+1) <= 2 * 2^(k+1)。代替，我們得到0.5 * 2^(k+1) = 2*2^(k-1) <= 2*Fibonacci(k-1) <= Fibonacci(k) + Fibonacci(k-1) <= 2*Fibonacci(k) <= 2 * 2^k <= 2 * 2^(k+1)。這完成了證明。

溶液的散列表（有時稱爲備忘錄，從那裏memoization的）防止從Fibonacci(k)被調用超過每k一次。由於Fibonacci(n)僅取決於Fibonacci(0)，Fibonacci(1)，...，Fibonacci(n-1)，並且由於哈希表和檢查防止這些被調用的次數超過一次，所以每次只調用一次，並且由於每個給定的工作量都是恆定的n，總工作量爲O(n)。再現關係現在很難考慮（我們有副作用和需要條件），所以我必須利用這種「詭計」的論點。不幸的是，大多數證明都需要某種「竅門」，歸納是一種例外。

來源

2017-10-17 20:56:17 Patrick87

如何確定包含優化的遞歸算法的大O？

回答

相關問題