大O记号

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

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

例如:

f(n) = 3n^2 + 2n +5 = O(n^2)

f(n) = \sqrt{5 n \cdot[3 n \cdot(n+2)+4]+6} = O(n^{1.5})

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

O(f(n)) + O(g(n)) = O(max(f(n),g(n)))

乘法规则:

O(f(n))\times O(g(n)) = O(f(n)\times g(n))

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

渐进记号 范围 含义
O f(n)\leq cg(n) 上界
\Theta c_1g(n)\leq f(n)\leq c_2g(n) 确界
\Omega cg(n)\leq f(n) 下界
o f(n)< cg(n) 非渐进上界
\omega cg(n)< f(n) 非渐进下界

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

循环的时间复杂度

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

例1:

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

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

n*n =O(n^2)

例2:

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

外层第1次循环,内层循环0次;
外层第2次循环,内层循环1次;

外层第n次循环,内层循环n-1次;

所以复杂度为:

0+1+\ldots+(n-1)=\frac{n(n-1)}{2}=O\left(n^{2}\right)

例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次;

所以复杂度为O\left(n^{2}\right)

例4:

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

当循环退出时sum=n,而sum = 1+2+3+...+i = (1+i)*i/2,所以当循环退出时(1+i)*i/2=n。因为每循环一次i就加1,所以i恰好是循环次数,所以循环次数与n^{1/2}同阶,所以复杂度为O(n^{1/2})

例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次,所以复杂度为O(n^2)

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

级数 执行级数次的复杂度
算术级数 1+2+\ldots+n=O\left(n^{2}\right)
幂方级数 1^{2}+2^{2}+3^{2}+\ldots+n^{2}=O\left(n^{3}\right)\qquad 1^{3}+2^{3}+3^{3}+\ldots+n^{3}=O\left(n^{4}\right)
几何级数 a^{0}+a^{1}+\ldots+a^{n}=O\left(a^{n}\right)\qquad 1+2+4+\ldots+2^{n}=O\left(2^{n}\right)
调和级数 1+1 / 2+1 / 3+\ldots+1 / n=\Theta(\log n)
对数级数 \log 1+\log 2+\log 3+\ldots+\log n=\Theta(n \log n)

递归的时间复杂度

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

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

每次递归都将规模减1,不难得出递归方程:
T(n)=T(n-1)+O(1)
T(0)=O(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);
}

每次递归转化为两个一半规模的问题,所以有递归方程:
T(n) = 2*T(n/2) + O(1)
T(1) = O(1)

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

封底估算

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

1天≈105sec
三生三世≈1010sec
宇宙至今≈1021sec

例如,冒泡排序的复杂度为O(n^2),使用1GHz的计算机对人口普查数据n = 10^9进行排序,需要多长时间?
(10^9)^2 /10^9 = 10^9
这个数字比1天大比三生三世小,大概几十年的样子

posted @ 2020-05-07 11:06:57
评论加载中...

发表评论