我最近做了一个测试...这个问题说来话长，解决方案归结为 F(n) = 2*F(n-1) + 2*F(n-2)...
我有一个使用动态编程的 O(n) 解决方案......但是，考官并不满意......
我的解决方案是在计算时将每个 F(n) 简单地存储在一个数组中。花了 O(n) 时间。由于我们只需要前两个元素，因此只需使用两个变量，就可以解决空间问题。
但是 O(n) 还不够快...
该函数看起来像斐波那契函数，并且可以在 O(lg n) 时间内生成一个斐波那契数......但我无法为我的问题获得 O(lg n) 求解。
所以我的问题是如何提高函数的时间复杂度？
完全相同的方式。以矩阵形式表达你的重复；这将问题减少到找到矩阵的 n 次方，这可以在 log(n) 时间内完成。
任何线性递推关系（就是这样）都有一个封闭的公式。
它涉及求解特征多项式，在这种情况下为：
t^2 - 2*t - 2 = 0 (since F(n) - 2 * F(n-1) - 2 * F(n-2) = 0)
如果 t1 和 t2 是该二次方程的（复）解，则公式为：
F(n) = a * t1^n + b * t2^n
其中 a 和 b 是常数，可以从初始条件（即本例中的 F(0) 和 F(1) 的值）中找到。IE
F(0) = a + b
F(1) = a * t1 + b * t2
求解 a 和 b：
a = ( t2 * F(0) - F(1) ) / ( t2 - t1 )
b = ( t1 * F(0) - F(1) ) / ( t1 - t2 )
在这种特殊情况下，特征多项式的根是：
t1 = 1 + sqrt(3)
t2 = 1 - sqrt(3)
在您的解决方案中，您还使用了 O(n) 内存。
您可以使用简单的循环来计算第 n 个斐波那契元素：
您唯一需要保存的是最后 3 个 (a1,a2,a3) 元素，在每次迭代中，您将 a1 更新为 a2，将 a2 更新为 a3，并将 a3 更新为 old(a1) + old(a2) （您可以为此使用 2 个临时变量）。
所以我们得到了运行时 O(n) 只有 O(1) 内存的简单算法。