算法学习四：算法性能分析理论基础——函数增长与渐进分析

在算法性能分析过程中，特别是在算法运行效率分析中，我们经常使用渐渐分析法，它使我们在分析算法性能时不必纠结于不同硬件平台的差异性，着重考虑算法的运行趋势。对于渐进分析的理论基础，了解过后才能真正明白这样做的可行性。首先需要掌握函数增长的渐进分析。

渐进的记号

Θ记号

之前在排序算法中知道插入排序的最坏情况下运行时间是Θ(n2)$Θ(n^2)$，现在我们可以解释这种记号的含义。
设有一个函数f(n)$f(n)$，用 Θ(g(n))$Θ(g(n))$ 表示如下的集合：
Θ(g(n))$Θ(g(n))$={f(n)$f(n)$ :存在正常数c1$c_1$，c2$c_2$和n0$n_0$，使对于所有的n≥n0$n ge n0$，有0<=c1g(n)≤f(n)≤c2g(n)$0<=c_1g(n)le f(n)le c_2g(n)$}，则f(n)$f(n)$ 属于集合Θ(g(n))$Θ(g(n))$，记作：
f(n)∈Θ(g(n)) $$f(n)∈Θ(g(n))$$
在前面引入了Θ的概念，其效果相当于舍弃了低阶项和忽略了最高项的系数，下面证明
12n2−3n=Θ(n2)$frac{1}{2}n^2-3n=Θ(n^2)$。首先要确定常系数c1$c_1$，c2$c_2$和n0$n_0$，使对于所有的n≥n0$n ge n0$，
c1n2≤12n2−3n≤c2n2 $$c_1n^2 le frac{1}{2}n^2-3n le c_2n^2$$
化简得
c1≤12−3n≤c2 $$c_1 le frac{1}{2}-frac{3}{n}le c_2$$
右边的不等式在c2≥12$c_2 ge frac{1}{2}$ 的时候恒成立，同样，左边的不等式令 n≥7$n ge 7$，则对于 c1≤114$c_1le frac{1}{14}$ 成立。即证明了 12n2−3n=Θ(n2)$frac{1}{2}n^2-3n=Θ(n^2)$。

O记号

Θ记号渐进地给出了一个函数的上界和下界，而当一个函数只有渐进上界时，需要使用O记号。对于一个函数g(n)$g(n)$ ，用 O(g(n))$O(g(n))$ 表示一个函数集合：
O(g(n))$O(g(n))$={f(n)$f(n)$ :存在正常数c1$c_1$和n0$n_0$，使对所有的n≥n0$n ge n_0$，有0≤f(n)≤c1g(n)$0 le f(n)le c_1g(n)$}。
注意f(n)=Θ(g(n))$f(n)=Θ(g(n))$ 隐含着 f(n)=O(g(n))$f(n)=O(g(n))$，因为Θ记号强于O记号，按集合论中的写法，有Θ(g(n))∈O(g(n))$Θ(g(n))∈O(g(n))$。

Ω记号

Ω记号渐进地给出了一个函数的渐进下界，对于一个函数g(n)$g(n)$ ，用 O(g(n))$O(g(n))$ 表示一个函数集合：
Ω(g(n))$Ω(g(n))$={f(n)$f(n)$ :存在正常数c1$c_1$和n0$n_0$，使对所有的n≥n0$n ge n_0$，有f(n)≥c1g(n)≥0$f(n)ge c_1g(n) ge 0$}。
注意f(n)=Θ(g(n))$f(n)=Θ(g(n))$ 隐含着 f(n)=Ω(g(n))$f(n)=Ω(g(n))$，因为Θ记号强于Ω记号，按集合论中的写法，有Θ(g(n))∈Ω(g(n))$Θ(g(n))∈Ω(g(n))$。

祝枫
2016年9月10日于哈尔滨