如何确定下列递归的大O时间复杂度: f(n) = f(n-1) + f(n-3) +c

Question

如何求解这个递归: f(n) = f(n-1) + f(n-3) + c其中c是常数f(1)=1

请帮我解决这个问题

Answer 1

我们显式地求解该函数。首先，将c添加到两端以获取

f(n) + c = (f(n - 1) + c) + (f(n - 3) + c)

定义g(n) = f(n) + c。则g的递归为

g(n) = g(n - 1) + g(n - 3)

请注意，由于g是由g(0), g(1), g(2)确定的，因此该方程的解集形成了一个3维的向量空间。因此，找到3个基本元素就足够了。

我们尝试对k非零值执行g(n) = k^n。对于这样的Ansatz，我们看到

k^n = k^(n - 1) + k^(n - 3)

换句话说，我们可以看到

k^3 = k^2 + 1

这个方程没有有理根，所以它的根会有点脏。原来有三个根，一个是实数，两个是复数。其根部大致为

x = 1.47

x = -0.233 +/- 0.793 i

因此，三个基本的解决方案是1.47^n和(-0.233 +/- 0.793 i)^n (大致)。

您实际上没有提供足够的信息来查找g，因为我们需要知道g(0)、g(1)和g(2)。但是对于基本的解决方案，很容易看到1.47^n = O(1.47^n)和(-0.233 +/- 0.793 i)^n = O(1)，因为|(-0.233 +/- 0.793 i)| < 1。

因此，在几乎所有的情况下(除了可以编写g(n) = a (-0.233 + 0.793 i)^n + b (-0.233 - 0.793 i)^n的情况)，我们都有g(n)= Theta(1.47^n)，因此也有f(n) = g(n) - c = Theta(1.47^n)。

请记住，1.47当然是一个近似值。真正的价值是k^3 = k^2 + 1的唯一真正的解决方案。