渐进分析

分析斐波那契计算的复杂度

斐波那契数列的定义

迭代的算法

int F(int n) {
    int less = 1, bigger = 1;
    int temp, i;
    for (i = 2; i < n; ++i) {
        temp = less + bigger;
        std::swap(less, bigger);
        bigger = temp;
    }
    return less + bigger;
}

时间复杂度为：

递归的算法

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

时间复杂度为：

对于这种递归的算法，可以将过程值储存起来，从而降低时间复杂度