如何計算動態規劃（Memoization）算法的大O O

我將如何去計算DP算法的大O。我已經意識到我的計算算法的方法並不總是奏效。我會用簡單的技巧來提取大O的內容。例如，如果我正在評估下面的算法沒有memoized版本（刪除緩存機制），我會看看遞歸方法在這種情況下自己調用3次的次數。然後我會將這個值提高到n（3^n）。由於遞歸堆棧不夠深，DP根本就不對。我的直覺告訴我，DP解決方案的大O將是O（n^3）。 我們如何口頭解釋我們如何得出這個答案。 更重要的是什麼是可以用來找到類似問題的大O的技術。由於它是DP，我相信子問題的數量很重要我們如何計算子問題的數量。如何計算動態規劃（Memoization）算法的大O O

public class StairCase { 
    public int getPossibleStepCombination(int n) { 
     Integer[] memo = new Integer[n+1]; 
     return getNumOfStepCombos(n, memo); 
    } 

    private int getNumOfStepCombos(int n, Integer[] memo) { 
     if(n < 0) return 0; 
     if(n == 0) return 1; 
     if(memo[n] != null) return memo[n]; 
     memo[n] = getNumOfStepCombos(n - 1, memo) + getNumOfStepCombos(n - 2, memo) + getNumOfStepCombos(n-3,memo); 
     return memo[n]; 
    } 
}

來源

2015-10-09 Marquis Blount

第一3線做什麼，但比較int值，通過索引來訪問的陣列，並查看是否Integer參考是null。這些都是O(1)，所以唯一的問題是該方法遞歸調用多少次。

這個問題非常複雜，所以我通常會作弊。我只是用櫃檯來看看發生了什麼。（我已經爲此做了靜態方法，但通常情況下，應儘可能避免靜態可變狀態）。

static int counter = 0; 

public static int getPossibleStepCombination(int n) { 
    Integer[] memo = new Integer[n+1]; 
    return getNumOfStepCombos(n, memo); 
} 

private static int getNumOfStepCombos(int n, Integer[] memo) { 
    counter++; 
    if(n < 0) return 0; 
    if(n == 0) return 1; 
    if(memo[n] != null) return memo[n]; 
    memo[n] = getNumOfStepCombos(n - 1, memo) + getNumOfStepCombos(n - 2, memo) + getNumOfStepCombos(n-3,memo); 
    return memo[n]; 
} 

public static void main(String[] args) { 
    for (int i = 0; i < 10; i++) { 
     counter = 0; 
     getPossibleStepCombination(i); 
     System.out.print(i + " => " + counter + ", "); 
    } 
}

這個程序打印

0 => 1, 1 => 4, 2 => 7, 3 => 10, 4 => 13, 5 => 16, 6 => 19, 7 => 22, 8 => 25, 9 => 28,

所以它看起來像最終計數器值由3n + 1給出。

在一個更復雜的例子中，我可能無法發現該模式，所以我在Online Encyclopedia of Integer Sequences中輸入前幾個數字(e.g. 1, 4, 7, 10, 13, 16)，我通常會進入包含該模式簡單公式的頁面。

一旦你以這種方式作弊找出規則，你可以設置關於理解爲什麼規則的作品。

下面是我如何理解3n + 1來自何處。對於n每一個值，你只需要做行

memo[n] = getNumOfStepCombos(n - 1, memo) + getNumOfStepCombos(n - 2, memo) + getNumOfStepCombos(n-3,memo);

恰好一次。這是因爲我們正在記錄結果，只有在答案尚未計算的情況下才執行此行。

因此，當我們從n == 5開始時，我們運行該行exacly 5次;一次爲n == 5，一次爲n == 4，一次爲n == 3，一次爲n == 2，一次爲n == 1。所以這是3 * 5 == 15次方法getNumOfStepCombos從自己被調用。該方法也從外部調用一次（從getPossibleStepCombination），因此總的調用次數爲3n + 1。

因此這是一個O(n)算法。

如果一個算法的行不是O(1)這個計數器方法不能直接使用，但你可以經常調整方法。

來源

2015-10-09 20:53:09

保羅的答案在技術上沒有錯，但有點誤導。我們應該通過函數如何響應輸入大小的變化來計算大O符號。保羅對O（n）的回答使複雜性看起來是線性時間，當它真的是表示數字n所需的比特數的指數時。例如，n = 10具有〜30個計算並且m = 2個比特。 n = 100具有〜300個計算並且m = 3個比特。 n = 1000具有〜3000個計算並且m = 4個比特。

我相信你的函數的複雜度是O（2^m），其中m是表示n所需的位數。我提到了很多我的答案https://www.quora.com/Why-is-the-Knapsack-problem-NP-complete-even-when-it-has-complexity-O-nW。

來源

2017-06-21 05:34:22 Amy

如何計算動態規劃（Memoization）算法的大O O

回答

相關問題