我最近做了一个测试...问题是长篇大论,解决方案归结为F(n)= 2*F(n-1)+ 2*F(n-2)......
我有一个使用动态编程的O(n)解决方案......但是,考官不满意......
我的解决方案是在计算时将每个F(n)存储在一个数组中.花了O(n)时间.因为我们只需要前两个元素,通过仅使用两个变量,就可以解决空间问题.
但是O(n)还不够快......
该函数看起来像斐波纳契函数,并且可以在O(lg n)时间内生成斐波纳契数...但是我无法获得O(lg n)soln来解决我的问题.
所以我的问题是如何改善功能的时间复杂度？