algorithm - 计算算法的执行时间

Question

我有这个算法:

S(n)
  if n=1 then return(0)
  else
    S(n/3)
    x <- 0
    while x<= 3n^3 do
       x <- x+3
    S(n/3)

2 * T(n/3) + n^3 是递归关系吗？

T(n) = O(n^3) 是执行时间吗？

Answer 1

递归表达式是正确的。该算法的时间复杂度为O(n^3)。

循环在 T(1) 处停止。

运行 n = 27 的示例有助于推导通用表达式:

T(n) = 2*T(n/3)+n^3 =
= 2*(2*T(n/9)+(n/3)^3)+n^3 =
= 2*(2*(2*T(n/27)+(n/9)^3)+(n/3)^3)+n^3 =
= ... =
= 2*(2*2*T(n/27)+2*(n/9)^3+(n/3)^3)+n^3 =
= 2*2*2*T(n/27)+2*2*(n/9)^3+2*(n/3)^3+n^3

从这个例子我们可以看出一般表达式为:

相当于:

反过来，可以求解为以下封闭形式:

此表达式中的主导项是 (1/25)*27n^3 (2^(log_3(n)) 是 O(n) ，您可以将其视为 2^(log(n)*(1/log(3)))；删除常量 1/log(3) 给出 2^log(n) = n)，因此，递归是 O(n^3)。