算法时间复杂度的表达-渐进符号与主定理（转载） | 斯人笔记本 - IMSRY

渐进符号是分析算法时间复杂度的常用记号，对于某个规模为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 符号对称, 这个下限的阶越高,结果就越有价值。

大Ω号的含义如下图所示：

大 Ω符号常用来分析某个问题或某类算法的时间下界。例如, 矩阵乘法问题的时间下界为 Ω( n^2) , 是指任何两个 n×n 矩阵相乘的算法的时间复杂性不会小于 n^2
, 基于比较的排序算法的时间下界为 Ω( nlog 2 n) ,是指无法设计出基于比较的排序算法, 其时间复杂性小于 nlog 2 n。

大 Ω符号常常与大 O 符号配合以证明某问题的一个特定算法是该问题的最优算法,或是该问题中的某算法类中的最优算法。

3、Θ(theta) ：紧确界
定义：若存在 3 个正的常数 c1 、 c2 和 n0 ,对于任意 n≥ n0 , 都有 c1f(n)≥ T(n)≥ c2f(n) , 则称 T( n) = Θ( f(n))。
Θ符号意味着 T( n)与 f( n)同阶, 用来表示算法的精确阶。

Θ符号的含义如下图所示。