• 主要使用渐进记号来描述算法的运行时间
• 渐进记号实际上应用于函数

ΘΩΟ

Θ记号

• $Θ(g(n))$表示函数集合

• 若存在正常数$c_1$和$c_2$，使得对于足够大的自然数$ n$ , 函数$f(n)$ 能夹入$c_1g(n)$ 与 $c_2g(n)$ 之间，则$f(n)$ 属于集合$Θ(g(n))$，可以记做$f(n)\inΘ(g(n))$ ，通常记 $f(n)=Θ(g(n))$ ，但本质是左边的。这样做的好处后面会知道？

• 函数f(n)在一个常量因子内等于g(n),称g(n)是f(n)的一个渐近紧确界
  

定理3.1

对任意两个函数f(n) 和g(n),我们有$f(n) = Θ(g(n))$,当且仅当$f(n)=O(g(n))$ 和$f(n)=Ω(g(n))$

$(n+a)^b = n^b + c_1 n^{b-1} + c_2 n^{b-2} + \cdots + a^b=\theta (n^b)$