具有三个递归调用的递归函数的时间复杂度

Question

具有以下递归关系的递归函数的时间复杂度是多少：

T(n) = T(n-1) + T(n-2) + T(n-3), T(0) = T(1) = 1 and T(2) = 2

我知道一个有两次递归调用的函数会给我们一个 O(2^n) 的指数时间复杂度，这是否意味着具有上述递归关系的函数会有 O(3^n) 的时间复杂度吗？

感谢您的帮助。

Answer 1

更具体地说，假设您有如下函数：

T(n) = T(n-1) + T(n-1) + T(n-1), T(0) = 1

这样写的时间复杂度正好是O(3^n).

你的函数比这个函数好一点，但时间复杂度是一样的O(3^n)

现在，如果我们像这样重写我建议的代码：

T(n) = 3 * T(n-1), T(0) = 1

复杂度仅为 O(n)！因为之前调用的结果是重复使用的，不需要再次调用。

所以在你的实现中，如果你可以让缓冲区不调用而只是使用以前调用的值（某些语言实际上可以支持这个）那么复杂度将降低到 O(n)。