algorithm - 递归的步数方法示例

Question

我需要找到斐波那契数列的递归算法的步数。谁能解释如何找到任何递归算法的步数？

fibo(n)
{
  if(n=2)
    return 1
  else
    return fibo(n-1)+fibo(n-2)
}

标签： algorithmtime-complexity

Answer 1

简单计算时 step 为 1，不需要计算时 step 为 0

                                              step
    1 fibo(n)                                   0
    2 {                                         0
    3  if(n=2)                                  1
    4    return 1                               1
    5  else                                     0
    6    return fibo(n-1)+fibo(n-2)             1+T(n-1)+T(n-2)
    7  }                                        0

如果 n=2 那么 1,2,3,4 行将只执行 1 次 所以对于 n=2

t(n)=  1*0 + 1*0 + 1*1 + 1*1

如果 n>2 行 1,2,3,5,6,7 将被执行，其中 3 和 6 的步长>0 所以第 3 和 6 行将贡献时间（否则部分采取 0 步。如果部分有计算和if 块的条件将决定是执行 if 部分还是 else 部分。这就是为什么我们计算 else 0)

so for n>2 
T(n)=1+1+T(n-1)+T(n-2)

T(n)={
        2 for n=2
        2+T(n-1)+T(n-2)  for n>2
      }