版本记录

前言

将数据结构和算法比作计算机的基石毫不为过，追求程序的高效是每一个软件工程师的梦想。下面就是我对算法方面的基础知识理论与实践的总结。感兴趣的可以看上面几篇。
1. 算法简单学习（一）—— 前言
2. 算法简单学习（二）—— 一个简单的插入排序
3. 算法简单学习（三）—— 分治法与合并排序
4. 算法简单学习（四）—— 冒泡排序

函数的增长

前面我们看到合并排序最坏情况的时间Θ（nlgn），插入排序最坏情况的时间为Θ（n^2），也就是说当n很大的时候，插入排序最坏情况是不如合并排序的，当输入规模很大的时候，我们可以认为算法的运行时间只与增长的量级有关，这时就是在研究算法的渐进效率。

几种渐近记号

用来表示算法的渐进运行时间的几号是用来定义域为自然数集N = {0, 1, 2 ... }的函数来定义的。下面我们就看一下几种基本的渐近几号和扩展用法。

1. Θ记号

前面我们知道插入排序最坏的情况下是T(n) = Θ(n²)，下面我们就定义这个符号的含义。

对于一个给定的函数g(n)，用Θ(g(n))来表示函数集合。Θ(g(n)) = {f (n) ： 存在正常数c₁ ，c₂，n₀，使对所有的n≥n₀，有0 ≤ c₁g(n) ≤ f (n) ≤ c₂g(n) }，对任一个函数f(n)，若存在正常数c₁ ，c₂，使当n充分大的时候，f (n) 能被夹在 c₁g(n)和c₂g(n)之间，则f (n) 属于集合Θ(g(n))。也可以说f (n)是Θ(g(n))的元素，可以写成f (n) = Θ(g(n)。

下面几个图给出了f(n)和g(n)的几种关系。

图1

图2

图3

下面说一下这几张图示。

• 图1：Θ记号限制一个函数在正常范围内，如果存在正常数c1 ，c2，n0，使对所有的n≥n0，有0 ≤ c1g(n) ≤ f (n) ≤ c2g(n)，就可以写作f (n) = Θ(g(n))。
• 图2：O记号给出一个函数在常数因子内的上限，如果存在正常数n₀和c，使得在n₀右边的f（n）的值永远等于或者小于cg（n），那么就可以写为f (n) = O(g(n))。
• 图3：Ω记号给出一个函数在常数因子内的下限，如果存在正常数n₀和c，使得在n₀右边的f（n）的值永远等于或者大于cg（n），那么就可以写为f (n) = Ω(g(n))。

2. O记号

Θ记号给出了上界和下界，当只有上界的时候用O记号表示。下面我们就给一下定义，其实前面那几张图基本已经说得很清楚了。

我们以O(g(n))表示一个函数集合，如果存在正常数n₀和c，使得在n > n₀时有 0 ≤ f(n) ≤ cg（n），那么就可以写为f (n) = O(g(n))。

3. Ω记号

Θ记号给出了上界和下界，当只有下界的时候用Ω记号表示。下面我们就给一下定义，其实前面那几张图基本已经说得很清楚了。

我们以Ω(g(n))表示一个函数集合，如果存在正常数n₀和c，使得在n > n₀时有 0 ≤ cg（n） ≤ f(n)，那么就可以写为f (n) = Ω(g(n))。

下面我们看一下定理。

定理1：对任意两个函数f(h)和g(n)，f (n) = Θ(g(n))当且仅当f (n) = O(g(n))和f (n) = Ω(g(n))。

定理的应用范围并不是根据上下界的范围确定渐近上界和渐近下界，而是用渐近上界和渐近下界证明出渐近确界。

等式与不等式中的渐进符号

如果等式或者不等式中有渐进符号，比如公式中：2n² + 3n + 1 = 2n² + Θ(n)，这就表示2n² + 3n + 1 = 2n² + f(n)，其中f(n)是某个属于集合Θ(n)的函数，在这里f(n) = 3n + 1，确实在Θ(n)中。

等式里的渐近符号的作用就是有助于略去一个等式中无关紧要的细节，比如说我们前面说过合并排序最坏情况的运行时间表示为递归式。

T(n) = 2T(n/2) + Θ(n)

如果只对T(n) 的渐进行为感兴趣，则没有必要写出所有的低阶项，它们都被包含在由Θ(n)表示的匿名函数中了。

1. o记号

O记号提供的渐近上界可能是也可能不是渐近精确的，比如说2n² = O(n²)就是渐近精确的，但是2n = O(n²）就不是，我们使用o记号来表示非渐近精确的上界，o(g(n))的形式定义为集合o(g(n)) = {f(n), 对任意正常数c，存在常数n₀ > 0，使对所有的n ≥ n₀，有 0 ≤ f (n) ≤ cg(n)}。例如， 2n = o(n²)，但是，2n² ≠ o(n²)。

这里还要说一下O和o的区别，二者不同的是，f (n) = O(g(n))，界0 ≤ f(n) ≤ cg（n）对某个常数c > 0成立，但是对f (n) = o(g(n))，界0 ≤ f(n) ≤ cg（n）对所有常数c > 0成立。可以认为o表示当n趋于无穷大时，函数f(n)相对于g(n)的极限。

2. ω记号

ω记号与Ω记号的关系就好像是o记号与O记号的关系一样，我们用ω记号来表示非渐近精确的下界。这里的定义就不给出了，具体可参考上面对o记号的定义。

函数的性质

许多关系属性可以应用于渐近比较，假设f(n)和g(n)是渐近正值函数。

1. 传递性

传递性

2. 自反型

自反性

3. 对称性

对称性

4. 转置对称性

转置对称性

因为这些性质对渐近记号也成立，我们可以将两个函数f和g的渐近比较和两个实数a与b的比较作一类比。

渐近比较

虽然任何两个实数都可以做比较，但并不是所有的函数都是渐近可比较的，也就是说，对于两个函数f(n)和g(n)，可能f(n) = O(g(n))和f(n) = Ω(g(n))都不成立，举个例子，函数n和n^(1 + sinn)无法利用渐近记号来比较，因为n^(1 + sinn)中指数的范围是 0 ~ 2。

后记

未完，待续~~~

树