来自算法的递归方程

Question

我今年 10 月开始攻读生物信息学硕士学位，对于一位前生物学家来说，从一段代码中找到递归方程非常困难。如果有人能给我解释一下，我将不胜感激。

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

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)。

我会用 iteration/recursion 树方法给你一个解决这个问题的机会。

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))

来自算法的递归方程

Recursive equation from algorithm

algorithm

recursion

recurrence

pseudocode