Fibonacci

https://www.zhihu.com/question/28062458
http://blog.csdn.net/hikean/article/details/9749391

对于Fibonacci数列，1，1，2，3，5，8，13，21...
F(0) ＝ 1， F(1) ＝ 1, F(i) = F(i-1) + F(i-2) 求解第n项。

1.递归

long fib(int n)
{
    if (n == 0 || n == 1)
    {
        return 1;
    }
​
    return fib(n - 1) + fib(n - 2);
}

这是最好写，也是效率最低的方法，时间复杂度是指数级别的。

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];
}

这个方法也是很容易想到的，时间复杂度是 O(n), 空间复杂度也是 O(n)。

3. 遍历优化版

fibs[n]只和前两个元素相关，因此任意时刻我们只要有前两项就可以了。这样空间复杂度可以做到 O(1)，我们用个循环数组就可以了。

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. 矩阵相乘

把一维问题拉到二维。

所以，

现在问题是如何快速计算一个矩阵的n次方。这里可以利用A^n = A^(n/2)*A(n/2) * (n % 2 == 1 ? A : I)进行分治。

matrix power(matrix A, int n)
{
    matrix ans = I;
    while(n > 0)
    {
        if (n % 2 == 1)
        {
            ans *= A;
        }
​
        A *= A;
        n /= 2;
    }
​
    return ans;
}

这个算法的时间复杂度是O(logN)。

5. 特征值分解

对于矩阵的 n 次方求解，可以通过矩阵的特征值分解来完成。过程如下：

6.差分方程求解

如果了解差分方程，那么这个解析解就很容易得到了。