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

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

乍一看，第 3 个分支比其他两个分支花费的时间更多，我可以忽略第 1 个和第 2 个分支吗？，所以复杂度可以是 T(n) =2*T(n-1)，结果是O(2^n)，我说得对吗？

此外，如果在第 2 个分支中还有一个 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);
    }

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

Answer 1

是的，你应该取它们的最大值(对于最坏的情况)，它对应于第三个分支。因此，您可以忽略第一个和第二个分支。然后，重复是T(n)<=2T(n-1)+O(1) ，所以 T(n)=O(2^n) .

出于同样的原因，您可以“免费”将新调用添加到第二个分支。