algorithm - 涉及两个递归调用时计算复杂度

Question

当有多个递归调用时如何计算复杂度？

比如这个问题。

F(n)
{
   if (n is 1)
     return;
   F(n/2)  //Call 1
   F(n/3)  //Call 2
   F(n/6)  //Call 3
}

Answer 1

你只需要解方程，

T(n)=T(n/2)+T(n/3)+T(n/6)+O(1)

现在因为 T(n/2)>T(n/3)，我们可以解决

T(n)=3T(n/2)+O(1)

使用大师定理，T(n)=O(n^(log(base 2)3))=O(n^1.58)

请注意，可能有更好的解决方案，但由于这是大 O 表示法，这也是有效的

Answer 2

有趣的问题。

我相信我可以证明对于任何 c > 1 ，这个函数的复杂度都是 O(n ^{c )。}

回想一下大 O 表示法的定义。如果存在常数 k 和 n' 使得 g(n) < k*f(n) 对于所有 n > n'，我们说函数 g(n) 是 O(f(n))。（通俗地说，对于足够大的 n，g(n) 以 f(n) 为界，忽略常数因子。）

选择任何 c > 1，并观察对于足够大的 n，

1 > (1/2) ^c + (1/3) ^c + (1/6) ^c + 1/n ^c

这很容易看出，因为 1/2 + 1/3 + 1/6 = 1，并且 (1/2) ^c < 1/2 等等，因为 c > 1。当 n 足够大时，1/n ^c是任意小。

乘以 n ^c，得到足够大的 n：

n ^c > (n/2) ^c + (n/3) ^c + (n/6) ^c + 1

因此，如果在m=n/2、m=n/3 和 m=n/6 的情况下，F(m) 的运行时间以 m ^c为界，则 F(n) 的运行时间为ñ ^c。结果通过归纳得出。

因此，虽然我错认为这个函数是 O(n)，但它是任意接近的......从某种意义上说，对于任何正值 epsilon，无论多么小，函数都是 O(n ^1+epsilon )。

...

一般来说，对于这类问题，我认为你想猜测 n ^c形式的解决方案，然后尝试在 c 上设置一个界限。这基本上就是主定理本身的工作原理。