面額任務遞歸算法的時間複雜度

Question

我計算1,2或5個數字的輸入數k的所有可能變體。這是理解的簡單算法：

//1,2,5 
func foo(k: Int, result: [Int] = []) { 
    if k == 0 { 
     print(result) 
     return 
    } 

    var one = result 
    one.append(1) 
    foo(k: k-1, result: one) 

    if k >= 2 { 
     var two = result 
     two.append(2) 
     foo(k: k-2, result: two) 
    } 

    if k >= 5 { 
     var five = result 
     five.append(5) 
     foo(k: k-5, result: five) 
    } 
} 

所以，它的工作原理。我的問題是這個算法的複雜性（大O）是什麼？ 我認爲它是3^k，因爲裏面有3次遞歸調用。 請證明或解釋你的意見。

Answer 1

你對O（3^n）的分析是正確的，但它不是一個緊密的界限，因爲儘管分支因子是（大部分）3，右分支（n-5）的高度小於中間值n-2）和左（n-1）分支。

描述你的代碼的遞推關係是：T(n) = T(n-1) + T(n-2) + T(n-5) + 1

減去T(n)T(n+1)（標準招擺脫固定的），我們得到：

T(n+1) - T(n) = T(n) + T(n-1) + T(n-4) + 1 - T(n-1) - T(n-2) - T(n-5) - 1 
T(n+1) = 2T(n) - T(n-2) + T(n-4) - T(n-5) 

This is a homogoneous linear recurrence relation, so has solutions of the form：

sum(A_i * a_i^n for i=0..5) 

其中A_i是（複數）常數，a_i是等式的根x^6 = 2x^5 - x^3 + x - 1.0因此，T（n）的增長順序爲O（a^n），其中a是方程的最大量級根。 That happens to be real, and is approximately 1.7049。

所以你的代碼運行在O（1.705^n）時間。這比O（3^n）好得多，儘管當然還是指數級的。

Answer 2

你說得對，分析有兩個關鍵。既然你k作爲它的參數定義函數，然後讓我們寫下的k在條款的複雜性：

對於k >= 5，FOO解決大小k的問題歸結爲一個自稱3次，以解決小題，每小題大小k - c，其中c是一個常數（在你的情況下最多5）。因此，你可以記下foo的時間複雜度爲：

3 * f(k-1) >= f(k) >= 3 * f(k-5) 

和解決方案顯然是f(k) = O(3^k)，這可以證明，例如通過測量遞歸樹葉的數量。