根据这个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);
}
如何计算这种情况下的时间复杂度?
最佳答案
是的,你应该取它们的最大值(对于最坏的情况),它对应于第三个分支。因此,您可以忽略第一个和第二个分支。然后,重复是T(n)<=2T(n-1)+O(1)
,所以 T(n)=O(2^n)
.
出于同样的原因,您可以“免费”将新调用添加到第二个分支。
关于algorithm - 具有多个分支的递归函数的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33490598/