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

Question

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

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

我知 Prop 有两次递归调用的函数会给我们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)。