斐波那契算法中的递归方程

Question

斐波那契算法中的递归方程

3

我希望找到递归公式来计算时间复杂度。

    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

另外，如何找到算法的基本情况？

- Mohd Alomar

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Steve Jessop · Accepted Answer

对于复杂度而言，这个例子中的基本情况通常并不重要。个人认为我可能会设置 T(0) = 1，T(1) = 1，因为没有什么需要零时间。但是看一下你的递归关系。它本身就是一个斐波那契式的序列，无论基本情况如何，它都将是指数级的。

基本情况的一般问题在于，您希望得到一个具体的答案（“计算 Fib(0) 需要多长时间？”），但实际上，在复杂度计算中，“时间单位”通常定义得很模糊。要精确，您应该将 T(0) 定义为一个常数 k_1，将 T(1) 定义为一个常数 k_2，并从那里开始工作。如果您需要数值来解决递归关系中的常数，那么可能出了些问题。

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

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