由菲波拉契数列想到的问题
问题1:
对于这样一个数列
f(1) = 1; f(2) = 1; f(3) = (1); f(4) = 2;... f(n) = f(n - 1) + f(n - 3);
能否找出一种时间复杂度为O(logN)的方法求数列的第n项?
问题2:
对如下更一般的数列
(1)
f(1) = f(2) = ... = f(k) = 1;
f(n) = f(n - 1) + f(n - 2) + ... + f(n - k);
(2)
f(1) = f(2) = ... = f(k) = 1;
f(n) = f(n - 1) + f(n - k);
能否找出时间复杂度为O(logN)的方法求数列的第n项?
[解决办法]
1 不是有公式么？算乘方的时候可以用二进制法降低复杂度到log(2) N
2 对于5次及以上的一元高次方程没有通用的代数解法，所以K>4的时候是没有公式可以套的
[解决办法]
是的,求菲波拉契数列的第n项可以用矩阵乘法在O(log(n))内求解(不考虑大数乘法的复杂度).
以菲波拉契数列来说.
fib(1) = fib(2) = 1; (1)
fib(n) = f(n - 1) + f(n - 2); (2)
把(2)写成矩阵相乘的形式:
| fib(n) | |1 1| |fib(n-1)|| |=| |*| | (3)|fib(n-1)| |1 0| |fib(n-2)|
[解决办法]
对于这个问题，分析计算复杂度的一个大问题是计算需要log(n)次大数乘法。
如果假设这个递推公式特征方程中范数（或者说绝对值）最大的根的范数为M
那么我们可以有个估计公式
|f(n)|<=b*M^n (其中b为一个常数)
也就是说，f(n)的长度同n成正比。通常我们认为对于大数乘法，充分好的算法做一次乘法的时间复杂度近似为O(nlog(n))
所以上面算法过程的时间复杂度可以认为大概为O(n*log(n)^2).
而如果直接用递推公式累加，那么时间复杂为O(n^2) (一次加法时间为O(n))
