https://www.zhihu.com/question/28062458
http://blog.csdn.net/hikean/article/details/9749391
對于Fibonacci數(shù)列，1篙悯，1，2，3，5辆亏，8杂瘸，13，21...
F(0) ＝ 1翔曲， F(1) ＝ 1, F(i) = F(i-1) + F(i-2) 求解第n項(xiàng)。
1.遞歸
long fib(int n)
{
if (n == 0 || n == 1)
{
return 1;
}
?
return fib(n - 1) + fib(n - 2);
}
這是最好寫劈愚，也是效率最低的方法瞳遍，時(shí)間復(fù)雜度是指數(shù)級別的。
2. 遍歷
long fib(int n)
{
if (n == 0 || n == 1)
{
return 1;
}
?
std::vector <long> fibs(2, 1);
for (int i = 2; i <= n; ++i)
{
fibs.push_back(fibs[i - 1] + fibs[i - 2]);
}
?
return fibs[n];
}
這個(gè)方法也是很容易想到的菌羽，時(shí)間復(fù)雜度是 O(n), 空間復(fù)雜度也是 O(n)掠械。
3. 遍歷優(yōu)化版
fibs[n]只和前兩個(gè)元素相關(guān)，因此任意時(shí)刻我們只要有前兩項(xiàng)就可以了注祖。這樣空間復(fù)雜度可以做到 O(1)猾蒂，我們用個(gè)循環(huán)數(shù)組就可以了。
long fib(int n)
{
if (n == 0 || n == 1)
{
return 1;
}
int fib[3];
fib[0] = fib[1] = 1;
int idx = 1;
for (int i = 2; i <= n; ++i)
{
idx = (idx + 1) % 3;
fib[idx] = fib[(idx + 2) % 3] + fib[(idx + 1) % 3];
}
?
return fib[idx];
}
4. 矩陣相乘
把一維問題拉到二維是晨。
所以肚菠，
現(xiàn)在問題是如何快速計(jì)算一個(gè)矩陣的n次方。這里可以利用A^n = A(n/2)*A(n/2) * (n % 2 == 1 ? A : I)進(jìn)行分治罩缴。
matrix power(matrix A, int n)
{
matrix ans = I;
while(n > 0)
{
if (n % 2 == 1)
{
ans *= A;
}
?
A *= A;
n /= 2;
}
?
return ans;
}
這個(gè)算法的時(shí)間復(fù)雜度是O(logN)蚊逢。
5. 特征值分解
對于矩陣的 n 次方求解，可以通過矩陣的特征值分解來完成箫章。過程如下：
6.差分方程求解
如果了解差分方程烙荷，那么這個(gè)解析解就很容易得到了。
