递推方程

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

原来这是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))