大O记号

要估算算法的复杂度，首先要解决如何度量复杂度的问题。

假设一个算法的复杂度关于数据规模n的函数为，我们需要找到一个函数，当数据规模足够大时，使，即是的一个上界，此时我们说这个算法的复杂度为。按照这种度量方法，会发现，低次项和常系数可以忽略。

例如：

时间复杂度有以下两条规则：
加法规则：

乘法规则：

时间复杂度还有其它的度量方法，不过它们不是很常用，了解即可：

代码中有两种结构会因为数据规模n的变化导致执行时间变化，一种是循环，另一种是递归。下面我们分别介绍两种结构的复杂度分析方法。

循环的时间复杂度

对于循环，一般用归纳或者根据终止条件计算出循环次数，然后求出复杂度。

例1:

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        O(1);

外层循环n次，外层每循环1次内层循环n次，所以复杂度为:

例2：

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        O(1);

外层第1次循环，内层循环0次；
外层第2次循环，内层循环1次；
......
外层第n次循环，内层循环n-1次；

所以复杂度为：

例3：

for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j+=2013)
        O(1);

外层第1次循环，内层循环1%2013次；
外层第2次循环，内层循环1%2013次；
......
外层第n次循环，内层循环(n-1)%2013次；

所以复杂度为

例4：

int func(int n){
    int i=0, sum=0;
    while(sum<n) sum += ++i;
    return i;
}

当循环退出时,而,所以当循环退出时。因为每循环一次i就加1，所以i恰好是循环次数，所以循环次数与同阶，所以复杂度为

例5：

int m=0,i,j;
for(i=1;i<=n;i++)
    for(j=1;j<=2*i;j++)
        O(1);

归纳法：
外层第1次循环，内层循环2次；
外层第2次循环，内层循环4次；
外层第3次循环，内层循环6次；
......
外层第n次循环，内层循环2n次；

内层共循环(2+2n)n/2次，所以复杂度为

熟记常见级数复杂度，有助于快速判断代码复杂度

递归函数一般列出递归方程，转换为数学问题求解。

int sum(int A[], int n){
    return (n<1) ? 0 : sum(A,n-1) + A[n-1];
}

每次递归都将规模减1，不难得出递归方程：

int sum(int A[], int lo, int hi){
    if (lo == hi) return A[lo];
    int mi = (lo + hi) >> 1;
    return sum(A, lo, mi) + sum(A,mi +1,hi);
}

每次递归转化为两个一半规模的问题，所以有递归方程：

递归方程的求解是数学问题，有的递归方程比较好求解，有的则比较难解，这里不再讨论。

有的时候我们知道了一个算法的复杂度,我们需要粗略估计其处理数据所需要的时间，这里给出几个比较的单位：

1天≈10⁵sec
三生三世≈10¹⁰sec
宇宙至今≈10²¹sec

例如，冒泡排序的复杂度为，使用1GHz的计算机对人口普查数据进行排序，需要多长时间？

这个数字比1天大比三生三世小，大概几十年的样子