计算函数的阶:

如: T ( n ) = a n 2 + b n + c T(n)=an^2 +bn+c T(n)=an2+bn+c

主导项: a n 2 an^2 an2,当输入大小n较大时，其它低阶项相对来说意义不大,系数a也相对来说意义不大

即：函数T(n)的阶为n 2

定义(同阶): 设f(n)和g(n)是正值函数。如果 ∃ c 1 , c 2 ; 0 , n 0 , ∀ n ; n 0 , c 1 g ( n ) ≤ f ( n ) ≤ c 2 g ( n ) \exist c1 , c 2 ;0, n_0 , \forall n;n_0 , c_1 g(n) \le f(n) \le c_2 g(n) ∃c1,c2>0,n0​,∀n>n0​,c1​g(n)≤f(n)≤c2​g(n)，则称f(n)与g(n)同阶，记作f(n)= θ \theta θ(g(n)) 。

证明同阶,找到n ,c1, c2使得他们满足定义

定义(低阶) 设f(n)和g(n)是正值函数。如果$ \exist c>0, n_0 , \forall n>n_0 , f(n)\le cg(n)$，则称f(n)比g(n)低阶或g( n )是 f ( n ) 的 上 界 ， 记 作 f ( n ) = O ( g ( n ) ) 。

证明低阶: 找到n ,c满足定义

O ( g ( n ) ) 代表复杂度上界是g(n), f ( n ) = O ( g ( n ) )代表f(n)的复杂度小于g(n),读作复杂度不超过g(n)

如果 f ( n ) = O ( n k ) f(n)=O(n^k ) f(n)=O(nk), 则称f(n) 是多项式界限的

定义(高阶) 设f(n)和g(n)是正值函数。如果 ∃ c ; 0 , n 0 , ∀ n ; n 0 , f ( n ) ≥ c g ( n ) \exist c;0, n_0 , \forall n;n_0 , f(n) \ge cg(n) ∃c>0,n0​,∀n>n0​,f(n)≥cg(n)，则称f(n)比g(n)高阶或g(n) 是f(n)的下界，记作f(n)= Ω \Omega Ω (g(n)) 。

证明高阶: 找到 n ,c 满足定义

Ω \Omega Ω (g(n))代表复杂度下界为g(n), 读作复杂度不低于g(n)

对于插入排序，我们可以说

– 最好运行时间是$\Omega ( n ) – 或 者 说 ， 运 行 时 间 是 (n) – 或者说，运行时间是