算法导论第三章函数的增长——关于OΘΩ的用法

举个例子，解决一个规模为的问题所花费的时间（或者所需步骤的数目）假设表示为：。当增大时，项将开始占主导地位，而其他各项可以被忽略。 举例说明：当，项是 项的1000倍大，因此在大多数场合下，省略后者对表达式的值的影响将是可以忽略不计的。

进一步看，如果我们与任一其他级的表达式比较，项的系数也是无关紧要的。例如：一个包含或项的表达式，即使 ，假定 ，一旦增长到大于1,000,000，后者就会一直超越前者（）。

或

并且我们就说该算法具有阶（平方阶）的时间复杂度。

】

一、定义及其图像解释：

1、 确界。f(n)最多不可以超过g(n)的一个常数倍c1，最少也不会少于g(n)的一个常数倍c2

2、 上界：

和的关系可以理解为是的一个上界，也可以理解为最终至多增涨的速度与一样快，但不会超过的增涨速度。

3、 下界：

这三个定义都有点别扭，以Θ为例。

∃C1， C2 > 0，使得当 n  >=n0(某一常数)时恒有

C1*g(n)  <= f(n) <=  C2*g(n);

N要求大于某个常数，只要任意取n足够大，就可以满足。难点在于如何构造出C1和C2.。注意：

1、C1 C2不唯一，只要证明这样的C1、C2存在就可以，不需要求得一个十分准确的C1 C2。

举例子来说：

㎡ + 2m +5  =Θ(㎡)

你可取C1 = 0.1，或者 0.01，取C2 = 10，或者100，当m > 10000的时候，满足定义。

2、Θ(㎡)是一个集合，它的元素是f(m)【C1*g(n)  <= f(n) <=  C2*g(n)】。严格来说，f（m）∈Θ(㎡)

二、另外两个符号

1、o(小o)：

2、(小Ω)：

注意：o与O的区别是在于，小o的C1是任意的，而大O的c1不是。

三、        函数之间的比较

1、传递性

2、自反性

3、对称性

4、转置对称性

5、有益的类比

区别：对于实数a、b， > 、 < 、=必定有一个是成立的。而对于函数f(n)、g(n)可能三者都不成立。

 6、 附加

常用的函数阶

下面是在分析算法的时候常见的函数分类列表。所有这些函数都处于趋近于无穷大的情况下，增长得慢的函数列在上面。是一个任意常数。

符号	名称
	常数（阶，下同）
	对数
	多对数
	线性，次线性
	为迭代对数
	线性对数，或对数线性、拟线性、超线性
	平方
	多项式，有时叫作“代数”（阶）
	指数，有时叫作“几何”（阶）
	阶乘，有时叫做“组合”（阶）

超链接:练习题和博客内容的PDF文档

【更多可以参考超链接提供的《算法导论》或者Rosen的《离散数学》关于本部分内容的介绍。】