递归函数运行时

Question

1.Given 即 T(0)=1, T(n)=T([2n/3])+c（在本例中 2n/3 是下限）。 T(n) 的 big-Θ 是什么？这只是简单的log(n)(base 3/2)。请告诉我如何得到结果。

2.Given代码

void mystery(int n) {
   if(n < 2)
      return;
   else {
      int i = 0;
      for(i = 1; i <= 8; i += 2) {
         mystery(n/3);
      }
      int count = 0;
      for(i = 1; i < n*n; i++) {
         count = count + 1;
      }
   }
}

根据主定理，大O界是n^2。但我的结果是 log(n)*n^2 (base 3) 。我不确定我的结果，实际上我真的不知道如何处理递归函数的运行时。就是简单的日志功能？

或者如果像在这段代码中一样怎么办 T(n)=4*T(n/3)+n^2？

干杯。

Answer 1

让我们做一些复杂性分析，我们会发现 T(n) 的渐近行为取决于递归的常数。

给定T(n) = A T(n*p) + C，加上A,C>0和p<1，让我们首先尝试证明T(n)=O(n log n)。我们试图找到 D 这样对于足够大的 n

T(n) <= D(n * log(n))

这会产生

A * D(n*p * log(n*p)) + C <= D*(n * log(n))

查看高阶项，这导致

A*D*p <= D

所以，如果 A*p <= 1，这有效，并且 T(n)=O(n log n)。

在A<=1这种特殊情况下我们可以做得更好，证明T(n)=O(log n):

T(n) <= D log(n)

产量

A * D(log(n*p)) + C <= D*(log(n))

查看高阶项，这导致

A * D * log(n) + C + A * D *log(p) <= D * log(n)

对于足够大的 D 和 n 是正确的，因为 A<=1 和 log(p)<0。

否则，如果 A*p>1，让我们找到 q 的最小值，使得 T(n)=O(n^q)。我们试图找到最小的 q 使得 D 存在

T(n) <= D n^q

这会产生

A * D p^q n^q + C <= D*n^q

查看高阶项，这导致

A*D*p^q <= D

满足这个的最小值q由

定义

A*p^q = 1

所以我们得出 T(n)=O(n^q) for q = - log(A) / log(p).

现在，给定 T(n) = A T(n*p) + B n^a + C，A,B,C>0 和 p<1，尝试证明 T(n)=O(n^q) 对某些 q。我们试图找到最小的 q>=a 这样对于一些 D>0,

T(n) <= D n^q

这会产生

A * D n^q p^q + B n^a + C <= D n^q

尝试 q==a，只有在

时才有效

ADp^a + B <= D

即T(n)=O(n^a) 如果 Ap^a < 1.

否则我们像以前一样得到Ap^q = 1，这意味着 T(n)=O(n^q) for q = - log(A) / log(p) .

Answer 2

对于(1)，递归求解为c log_3/2 n + c。要看到这一点，您可以使用迭代方法展开一些递归项并找出一个模式：

T(n) = T(2n/3) + c

= T(4n/9) + 2c

= T(8n/27) + 3c

= T((2/3)^k n) + kc

假设 T(1) = c 并求解使括号内的表达式等于 1 的 k 的选择，我们得到

1 = (2/3)^k n

(3/2)^k = n

k = log_3/2

将 k 的选择代入上述表达式给出最终结果。

对于 (2)，你有递推关系

T(n) = 4T(n/3) + n²

使用主定理 a = 4, b = 3, d = 2，我们看到 log_b a = log3 4 < d,所以这解决了 O(n²)。这是一种查看方式。在顶层，你做 n² 工作。在那层下面，你有四个调用，每个调用做 n² / 9 工作，所以你做 4n² / 9 工作，少于顶层。下面的层执行 16 个调用，每个调用执行 n² / 81 次，总共执行 16n² / 81 次，再次比层之上。总的来说，每一层所做的工作都比它上面的层少得多，所以顶层最终逐渐支配所有其他层。

递归函数运行时

Recursive function runtime

algorithm

big-o