int multiplyRec(int m, int n){ if(n == 1) return m; 的复杂度是多少？返回 m + multiplyRec(m, n - 1); }

Question

以下递归关系的时间复杂度是多少？如何？

int multiplyRec(int m, int n){
if(n == 1)
    return m;
return m + multiplyRec(m,  n - 1);  

}

Answer 1

我认为它是 O(n)，但如果用 n 调用该函数则不是 < 1 - in that case you'll get stack overflow error

Answer 2

如果递归算法的每个函数调用都占用 O(m) 空间，并且递归树的最大深度为“n”，则递归算法的空间复杂度将为 O(nm)。

Answer 3

它是 O(n)，因为这里我们计算 T(n) = K + T(n-1) 等等，这里 k 是常数。

Answer 4

enter code here =

o(n) 因为 T(n)=k1+k2+T(n-1) :k1+k2=K 所以我们有 T(n)=K+T(n-1) 通过代入法可得 T(n)=k(n+1) T(n)= k*n 因为忽略项 k 所以时间复杂度是 o(n)

Answer 5

O(n) 递推关系为 T(n)= K+ T(n-1) 这里 k 是常数项 我们以线性方式搜索。

Answer 6

它是 O(n)，因为这里我们计算 T(n) = K + T(n-1) 等等，这里 k 是常数。

其中 K 等于 m 并且它只是占用额外的空间，而不是你可以使用 for 循环来改进它

但它需要 O(N) 为什么？

示例 n=5,m=1;

1.r(5) 1+r(4) 2.r(4) 1+r(3) 3.r(3) 1+r(2) 4.r(2) 1+r(1) 5.完成r(1) 返回 1 6.完成r(2) 1+1 = 2 ,返回2 7.完成r(3) 1+2 = 3 ,返回 3 8.完成r(4) 1+3 = 4 ，返回 4 9.完成r(5) 1+4 = 5

因此 5 就是答案，这里你可能认为有 9 个步骤，但我仍然说它需要 O(n) 时间 这是因为调用函数需要时间，我们不计算返回时间