algorithm - 来自算法的递归方程

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