algorithm - 具有多个分支的递归函数的时间复杂度

根据这个“AA>”，我们知道如何确定递归函数的复杂度。
但是，对于下面的代码，

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)，对吗？
此外，如果在第二个分支中还有一个find_path调用呢

    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);
    }

在这种情况下如何计算时间复杂度？

最佳答案

是的，你应该把它们的最大值（最坏的情况）对应于第三个分支。因此，您可以忽略第一和第二个分支然后，复发是T(n)<=2T(n-1)+O(1)，所以T(n)=O(2^n)。
出于同样的原因，您可以将新呼叫“免费”添加到第二个分支。