数据结构之算法和算法分析[4]

一个算法是由控制结构和原操作构成的其执行时间取决于两者的综合效果为了便于比较同一问题的不同的算法通常的做法是从算法中选取一种对于所研究的问题来说是基本运算的原操作以该原操作重复执行的次数作为算法的时间度量一般情况下算法中原操作重复执行的次数是规模n的某个函数T(n)

许多时候要精确地计算T(n)是困难的我们引入渐进时间复杂度在数量上估计一个算法的执行时间也能够达到分析算法的目的

定义(大Ο记号)如果存在两个正常数c和n使得对所有的nn≥n有

f(n) ≤ cg(n)

则有

f(n) = Ο(g(n))

例如一个程序的实际执行时间为T(n)=n+n+则T(n)=Ο(n)

使用大Ο记号表示的算法的时间复杂度称为算法的渐进时间复杂度(Asymptotic Complexity)

通常用Ο()表示常数计算时间常见的渐进时间复杂度有

Ο()<Ο(logn)<Ο(n)<Ο(nlogn)<Ο(n)<Ο(n)<Ο(n)

[] [] [] [] []