具有多個分支的遞歸函數的時間複雜度

Question

根據此post，我們知道如何確定遞歸函數的複雜性。

但是，下面的代碼，

const int N = 100, W = 100000; 
int p[N][W + 1]; // the values of element in the array p are 0, 1, 2. 
int output[N]; 

void find_path(int n, int w, int k) { 
    if (n < 0) { 
     for (int i=0; i<k; ++i) cout << output[i]; 
     return; 
    } 

    if (p[n][w] == 0) { 
     find_path(n-1, w, k); // the 1st branch 
    } 
    else if (p[n][w] == 1) { 
     output[k] = n; 
     find_path(n-1, w-weight[n], k+1); // the 2nd branch 
    } 
    else if (p[n][w] == 2) { 
     output[k] = n;     // the 3rd branch 
     find_path(n-1, w-weight[n], k+1); 
     find_path(n-1, w, k); 
    } 
} 

這裏是我的分析：

T(n) = T(n-1) + a // the 1st branch 
     T(n-1) + b // the 2nd branch 
     2*T(n-1) + c // the 3rd branch 

乍看之下，第三分支花費更多的時間比其他兩個分支，莫非我只是忽略第一和第二分支？，所以複雜度可能是T(n)=2*T(n-1)，結果是O(2^n),對嗎？

而且，如果有什麼是在第二分支

else if (p[n][w] == 1) { 
     output[k] = n; 
     find_path(n-1, w-weight[n], k+1); // the 2nd branch 
     find_path(n-1, w, k+1); 
    } 

如何計算在這種情況下，時間複雜多了一個find_path調用？

Answer 1

是的，你應該採取他們的最大值（對於最壞的情況），這對應於第三個分支。因此，您可以忽略第1和第2分支。那麼，再發現是T(n)<=2T(n-1)+O(1)，所以T(n)=O(2^n)。

出於同樣的原因，你可以添加新的電話到第二個分支「免費」。