算法时间复杂度的表达-渐进符号与主定理（转载）

渐进符号是分析算法时间复杂度的常用记号，对于某个规模为n的问题，当n足够大时，就可以忽略掉复杂度表达式中的低阶项和最高次项的系数，由此引出“渐进复杂度”，并且用渐进符号来对“渐进复杂度”进行表达。

一、渐进符号

1、O(大O符号）：上界
定义：若存在两个正的常数 c 和 n0 , 对于任意 n≥n0 , 都有 T( n)≤cf( n) ,则称T( n) = O( f( n) )(或称算法在 O( f( n))中)。

大 O 符号用来描述增长率的上限,表示 T( n)的增长最多像 f( n)增长的那样快,也就是说, 当输入规模为 n时, 算法消耗时间的最大值,这个上限的阶越低, 结果就越有价值。上界是对算法效率的一种承诺。

大O符号的含义如下图所示：

2、Ω（大Ω符号）：下界
定义：若存在两个正的常数 c和 n0 ,对于任意 n≥ n0 , 都有 T( n)≥cg( n) ,则称T( n) = Ω( g( n) )(或称算法在 Ω( g( n) )中)。

大 Ω符号用来描述增长率的下限, 也就是说, 当输入规模为 n 时,算法消耗时间的最小值。与大 O 符号对称, 这个下限的阶越高,结果就越有价值。

阅读剩下更多