0x01 书籍和算法

文明的传播，科技的兴起，工业***萌芽，都可以归功于印刷术的出现，而另一些人认为这一切的关键是算法的发展。

0x02 大O符号

大O符号(Big O notation)， 又称渐进符号，是用于描述函数的渐近行为的数学符号。它是指用另一个(通常更简单的)函数来描述一个函数数量级的渐进上界。

0x03 斐波那契数列

数列公式

F(n) = F(n-1)+F(n-2) if n> 1
F(n) = 1 if n=1
F(n) = 0 if n=0

n种解法

为了避免考虑整数溢出问题，我们将结果%1000000007。

递归

递归计算的节点个数是 O(2^n) 的级别的，存在大量重复计算。
时间复杂度是 O(2^n)，一秒内大约能算到第三四十项。

const int MOD = 1000000007;
int f(int n)
{
    if (n <= 1) return 1;
    return (f(n - 1) + f(n - 2)) % MOD;
}

记忆化搜索。

开一个大数组记录中间结果，如果一个状态被计算过，则直接查表，否则再递归计算。
总共有 n 个状态，计算每个状态的复杂度是 O(1)，所以时间复杂度是 O(n)。
一秒内算 n=10^7 毫无压力，但由于是递归计算，递归层数太多会爆栈，大约只能算到 n=10^5 级别。

const int N = 100000, MOD = 1000000007;
int a[N];
int f2(int n)
{
    if (a[n]) return a[n];
    if (n <= 1) return 1;
    a[n] = f2(n - 1) + f2(n - 2);
    a[n] %= MOD;
    return a[n];
}

递推

开一个大数组，记录每个数的值。用循环递推计算。
总共计算 n 个状态，所以时间复杂度是 O(n)。
但需要开一个长度是 n 的数组，内存将成为瓶颈，当 n=10^8 时，需要的内存是 4∗10^8x1024×1024≈381MB。
分子中乘4是因为C++中 int 类型占4字节。

const int N = 100000000, MOD = 1000000007;
int f3(int n)
{
    a[0] = a[1] = 1;
    for (int i = 2; i <= n; i ++ )
    {
        a[i] = a[i - 1] + a[i - 2];
        a[i] %= MOD;
    }
    return a[n];
}

递推+滚动变量

仔细观察我们会发现，递推时我们只需要记录前两项的值即可，没有必要记录所有值，所以我们可以用滚动变量递推。
时间复杂度还是 O(n)，但空间复杂度变成了 O(1)。

const int MOD = 1000000007;
int f4(int n)
{
    int x, y, z;
    x = y = 1;
    for (int i = 2; i <= n; i ++ )
    {
        z = (x + y) % MOD;
        x = y;
        y = z;
    }
    return z;
}