t(n)=t(n-1)+t(n-2)+t(n-3)的时间复杂度是多少？

Question

说 t(n)=t(n-1)+t(n-2)+t(n-3) 递归的时间复杂度是 3^n 的量级是否正确？

我画了递归树，得出了 3^i 的 sigma，其中 i 从 0 到 n，结果为 O(3^n)，有人可以纠正我吗？

Answer 1

是的，你的分析是正确的。如果您绘制了递归树并观察到每个级别的分支因子为

3

，则得出

3^i

的总和，其中

i

的范围从

0

到

n

（代表递归级别），那么时间复杂度确实是

O(3^n)

考虑到 t(n) 是一个简单的尾递归

为递归关系创建递归树

t(n) = t(n-1) + t(n-2) + t(n-3)

          t(n)
     ______|______
    |     |      |
  t(n-1) t(n-2) t(n-3)
    |     |      |
  t(n-2) t(n-3)  .
    |     |      .
  t(n-3)  .
    |     .
   ...    .

对于递推关系

t(n) = t(n-1) + t(n-2) + t(n-3)

，我们可以分析时间复杂度如下：

• 在每个递归级别，函数都会进行三次递归调用

  (t(n-1), t(n-2), and t(n-3))

  。

• 每层的分支因子为3，递归树的高度对应n的值。

• 递归树中的节点总数是指数级的，并且以O(3^n)的速度增长，它代表了递归调用的次数。

因此，算法的时间复杂度为

O(3^n)

。