以下函数的时间复杂度是多少?
int f = (int n) => {
if (n === 1) {
return 1;
}
for (let i = 0; i < n; i++) {
console.log(i);
}
return f(n-1) + f(n-1)
}
这是递归树的样子,其中i
表示深度:
f(4) // i = 0
/ \
/ \
/ \
/ \
/ \
f(3) f(3) // i = 1
/ \ / \
/ \ / \
f(2) f(2) f(2) f(2) // i = 2
/ \ / \ / \ / \
f(1) f(1) f(1) f(1) f(1) f(1) f(1) f(1) // i = 3
如果函数内部没有循环,时间复杂度将为 O(2^n)
。但是现在有一个循环所以:
在每个深度,进行的函数调用次数是 2 ^ i
并且在每个函数调用中 n - i
迭代是在循环中完成的,因此在每个级别(2 ^ i) * (n - i)
操作正在完成。因此,时间复杂度可以计算为:
T(n) = [(2 ^ 0) * (n - 0)] + [(2 ^ 1) * (n - 1)] + [(2 ^ 2) * (n - 2)] + ... + [(2 ^ (n - 1)) * (n - (n - 1))]
那么我的看法是否正确,最终的时间复杂度可能是多少?
最佳答案
你是对的,日志调用的数量是由重复驱动的
T(n) = C1 n + C2 + 2 T(n-1)
T(1)=C3
。
我们可以猜测解的形式为
T(n) = A 2^n + B.n + C
并通过识别,
T(n) = A 2^n - C1 n - C2 + C1.
最后,
T(1) = 2 A - C2 = C3
给出 A
。
关于algorithm - 带循环的递归函数的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/70492843/