algorithm - 斐波那契算法的递归方程

Question

我想找到递归方程来计算时间复杂度

    int Fib(int n)
{
    if (n <= 1)
        return n;
    else
        return Fib(n - 1) + Fib(n - 2);
}

我可以求解递推方程，但我很难找到方程和基本情况。

这是正确的方程式吗？

T(n)=T(n-1)+T(n-2)+1

对于基本情况？

T(0)=0

T(1)=0

通常如何找到算法的基本情况？

Answer 1

对于复杂性，此示例中的基本情况通常无关紧要。就我个人而言，我可能会设置T(0) = 1, T(1) = 1, 基础上什么都不需要零时间。但只要看看你的递归关系。它本身就是一个斐波那契风格的序列，无论基本情况如何，它都将是指数的（几乎）。

基本情况的一般问题是您想要一个具体的答案（“计算需要多长时间Fib(0)？”），但复杂性计算中的实际“时间单位”通常定义不明确。准确地说，您应该定义 T(0) 等于一个constant k_1，并且 T(1) 等于一个constant k_2，然后从那里开始工作。如果您需要常量的数值来解决递归关系，那么可能出现了问题。

同样，您可以将循环关系设置为T(n) = T(n-1) + T(n-2) + k_3。

请注意，如果您的复杂性计算的“时间单位”是“加法执行次数”，忽略其他逻辑，那么您的基本情况在0. 如果（例如）添加是由性能超出分析范围的用户提供的函数完成的，这将是一种分析时间的有用方法。