来自算法的递归方程

今年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），这是因为第一，如果条件需要恒定时间c和第一for循环是执行从1至8递归情况下，因此8 * T（n/2），但我不知道如何将最后一行代码添加到我的公式中。

来源

2017-11-11 Peet

语言标签请问？ –

@Peet .:'为1 < - 1'还是别的？ – coderredoc

我觉得这个问题不清楚。你需要使用递归符号来描述时间复杂性吗？我猜这个语言只是直观的伪代码 – storaged

你很近，但那不是很完美。

通常，递归关系只描述了递归过程的递归步骤所完成的工作，因为它假定基本情况的工作量是恒定的。因此，你会想看看

由和以什么递归调用它们是由什么尺寸输入，
多少工作的那个之外完成。

您已经正确识别出在输入大小为n/2时有8个递归调用，所以8T（n/2）项是正确的。但是，请注意，此操作后跟O（n ）工作的循环。其结果是，你的递归函数被更准确地建模为

T（N）= 8T（N/2）+ O（N 3 ）。

它是那么值得看，如果你可以争辩说为什么这解决了复发至O（N 日志N）。

来源

2017-11-11 15:32:06 templatetypedef

你刚刚开始写的时候......：）我是一个很慢的枪它似乎 – coderredoc

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

来源

2017-11-11 15:57:11 coderredoc

来自算法的递归方程

回答

相关问题