首页 > 专题系列 > 算法分析 > 算法-渐进分析
2014
04-03

算法-渐进分析

为什么会使用渐进来分析算法的效率,由于当问题的规模很小的时候,基本上在任何一台机器上都会以很快的速度计算出来,由于算法是机器无关的,编译器无关的,所以只有在问题规模较大的时候分析算法的效率才显得有意义。渐进就是将问题的规模趋向于无穷大,这样,对于系数,低阶项和常数项都是可以忽略的,因为随着问题规模逐渐趋向于无穷,这些项对于主导项来说,是完全可以忽略的。

对于算法来说,它的运行效率有三种情况,最好情况,平均情况和坏情况。一般我使用最坏情况下的复杂度来衡量算法效率,以保证可以包括所有的情况。

在以下的函数中,n表示的程序的输入数据的规模,对于不同的输入算法的效率可能是不一样的。

1.渐进性态

设T(n)为算法A的时间复杂性函数(输入值固定. 如Tmax, Tmin, Tavg ), 则它是n 的单增函数。

如果存在一个函数 W(n) 使得当n  -> ∞,有  (T(n) - W(n) ) / T(n) -> 0 称W(n) 是T(n)当 n  -> ∞时的渐进性态 或 渐进复杂性

例如   T(n)=3n^2+4nlogn+7,  则  W(n)可以是3n^2.

2.渐进分析符号

设f(n)和 g (n) 是定义在正整数集上的正函数.

1)大O表示法 (算法运行时间的上限 )

若存在正常数c 和 自然数N0 使得当 n >= N0 时,有f(n) <= c g (n)   则称函数 f(n )在n充分大时有上界, 且 g(n)是它一个上界. 记为 f(n) =O(g (n)) , 也称 f(n) 的阶不高于g (n) 的阶.

f 和g 的关系可以理解为g(n)f(n)的一个上界,也可以理解为f最终至多增涨的速度与g一样快,但不会超过g的增涨速度。

例如 3n=O(n),    n+1024=O(n),   2n^2 +11n-10=O(n^2)

2) 大Ω表示法 (算法运行时间的下限)

定义与大O符号的定义类似.

若存在正常数c和自然数N0使得当 n  >=  N0 时, 有f(n) >= c g(n)  , 则称函数f(n)在n充分大时有下限,  且 g(n)是它的一个下限, 记为f(n) = W (g (n) )  也称f (n)的阶不低于 g(n)的阶.

但主要区别是,大O符号表示函数在增长到一定程度时总小于一个特定函数的常数倍,大Ω符号则表示总大于。

用数学语言描述即是,f(\nu)=\Omega[g(\nu)]若存在x_1, \kappa使得:对于所有\forall x>x_1, f(x)>\kappa g(x).

大O与大Ω关系:大Ω符号与大O符号正好相反,即:\begin{cases}f(\nu)=\Omicron[g(\nu)]\\g(\nu)=\Omega[f(\nu)]\end{cases}

实际应用中,我一般是不用Ω表示法的,因为考虑最好的执行情况意义并不太大。

3) 大Θ符号

是大O符号和大Ω符号的结合。即:f(\nu)=\Theta[g(\nu)]\!\begin{cases}f(\nu)=\Omicron[g(\nu)]\\f(\nu)=\Omega[g(\nu)]\end{cases}

f (n) =Θ(g(n) ) 等价于  f(n)=O(g (n) ) 且 f(n)=Ω(g (n) )  称函数f(n)与g(n) 同阶.

一般情况下去掉 低阶项 和 常数系数就行了。

举例分析

已插入排序为例,时间复杂度最好的情况是线性的,最快情况是 O(n^2)。

如果我们使用θ符号来表示插入排序的时间复杂度,我们必须使用两个语句:

1。最坏的情况下插入排序的时间复杂度θ(n ^ 2)。

2。最好的情况下插入排序的时间复杂度θ(n)。

因此我们说时间复杂度是O(n^2)更为方便,因为O(n^2)也是包括线性时间。

参考MIT视频课程:课程简介及算法分析


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  2. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?