来自算法的递归方程

Question

我今年十月开始攻读生物信息学硕士学位，因为一位前生物学家从一段代码中找到递归方程非常困难。如果有人能向我解释这一点，我将不胜感激。

如何从这段代码中找到递归方程？

procedure DC(n)
   if n<1 then return
   for i <- 1 to 8 do DC(n/2)
   for i <- 1 to n³ do dummy <- 0

我的猜测是 T(n( = c + 8T(n/2(，因为第一个 if 条件需要常量时间 c，第一个 for 循环是从 1 到 8 执行的递归情况，因此 8*T(n/2(，但我不知道如何将最后一行代码添加到我的等式中。

Answer 1

你很接近，但事实并非如此。

通常，递归

关系仅描述递归过程的递归步骤所做的工作，因为它假定基本情况执行恒定量的工作。因此，您需要查看

• 进行了哪些递归调用以及它们在什么大小的输入上进行，以及
• 除此之外还做了多少工作。

您已经正确识别了大小为 n/2 的输入上有八个递归调用，因此 8T(n/2( 项是正确的。但是，请注意，这后面跟着一个执行 O(n³( 工作的循环。因此，您的递归函数更准确地建模为

T(n( = 8T(n/2( + O(n³(。

那么值得一看的是，如果你能争论为什么这种重复会解决 O(n³ log n(。

Answer 2

事实证明这是T(n)= 8*T(n/2)+O(n^3).

我将用迭代/递归树方法解决这个问题。

T(n) = 8* T(n/2) + O(n^3)
     ~ 8* T(n/2) + n^3
     = 8*(8* T(n/4) + (n/2)^3))+n^3
     = 8^2*T(n/4)+8*(n/2)^3+ n^3
     = 8^2*T(n/2^2)+n^3+n^3
     = 8^2( 8*T(n/8)+(n/4)^3)+n^3+n^3
     = 8^3*T(n/2^3)+ n^3 + n^3 + n^3
     ...
     = 8^k*T(n/2^k)+ n^3 + n^3 + n^3 + ...k time ...+n^3

这将在n/2^k=1 or k=log_2(n)时停止。

所以复杂性是O(n^3log(n))