程序算法艺术与实践:基础知识之函数的渐近的界

众所周知,算法所需的时间应当是随着其输入规模增长的，而输入规模与特定具体问题有关。对大多数问题来说其最自然的度量就是输入中的元素个数。算法的运行时间是指在特定输入时所执行的基本操作数。我们可以得到关于一个关于输入规模n的所需时间的函数。然而可以进一步简化算法的时间分析，我们进行进一步抽象，首先，忽略每条语句的真实代价，通过运行时间的增长率来度量一个算法在时间方面的表现。我们只考虑公式的最高次项，并忽略它的常数系数。本博文主要介绍一些相关的数学知识即:函数的渐近的界的定义与性质.常用的证明方法. ### 渐近符号 当输入规模大到使运行时间只和增长的量级有关时，就是在研究算法的 渐近 效率。就是说，从极限角度看，我们只关心算法运行时间如何随着输入规模的无限增长而增长。表示算法的渐近运行时间的记号是用定义域为自然数集 N = {0， 1， 2， …} 的函数来定义的。这些记号便于用来表示最坏情况运行时间 T ( n )。 #### *Θ* 记号(**读音:theta**) 对一个给定的函数 *g* ( *n* )，用 *Θ* ( *g* ( *n* ))来表示函数集合：  对任何一个函数 *f* ( *n* )，若存在正常数 *c1* ， *c2* ，使当 *n* 充分大时， *f* ( *n* )能被夹在 *c1 g* ( *n* )和 *c2 g* ( *n* )之间，则 *f* ( *n* )属于集合 *Θ* ( *g* ( *n* ))。可以写成“ *f* ( *n* ) ∈ *Θ* ( *g* ( *n* ))”表示 *f* ( *n* )是 *Θ* ( *g* ( *n* ))的元素。不过，通常写成“ *f* ( *n* ) = *Θ* ( *g* ( *n* ))”来表示相同的意思。  上图给出了函数 *f* ( *n* )和 *g* ( *n* )的直观图示，其中 *f* ( *n* ) = *Θ* ( *g* ( *n* ))。对所有位于 *n0* 右边的 *n* 值， *f* ( *n* )的值落在 *c1 g* ( *n* )和 *c2 g* ( *n* )之间。换句话说，对所有的 *n* >= *n0* ， *f* ( *n* )在一个常数因子范围内与 *g* ( *n* )相等。我们说 *g* ( *n* )是 *f* ( *n* )的一个 **渐近确界**。*Θ* ( *g* ( *n* ))的定义要求每个成员 *f* ( *n* ) ∈ *Θ* ( *g* ( *n* ))都是 **渐近非负**，就是说当 *n* 足够大时 *f* ( *n* )是非负值。这就要求函数 *g* ( *n* )本身也是渐近非负的，否则集合 *Θ* ( *g* ( *n* ))就是空集。*Θ* 记号的效果相当于舍弃了低阶项和忽略了最高阶项的系数。 #### *O* 符号 *Θ* 记号渐近地给出了一个函数的上界和下界。当只有 **渐近**上界时，使用 *O* 记号。对一个函数 *g* ( *n* )，用 *O* ( *g* ( *n* ))表示一个函数集合：  上图说明了 *O* 记号的直观意义。对所有位于 *n0* 右边的 *n* 值，函数 *f* ( *n* )的值在 *g* ( *n* )下。 [![clip_image002[10]](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/5830ff47f8743bc1ec107f4666226ffb_104x42.png "clip_image002[10]")](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192011436308.png)， 则可以表示为 f(n) = O(n2)。证明：要使得 0 <= f(n) <= cg(n)      [![clip_image002[12]](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/0bab581d328aa6eb03c99486016c950f_198x42.png "clip_image002[12]")](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192011542187.png) [](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192012001003.png) [](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192012005605.png) 存在c = 9/2 ,n0 = 1,使得对所有的n >= n0都有 0 <= f(n) <= cg(n)。O(g(n) 以及后面讲到的记号表示的都是集合，而f(n) = O(n2)的实际意义 是 f(n) ∈ O(n2)。假设有 [![clip_image002[14]](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/1a837264b2834af446bb6e81a3131268_90x31.png "clip_image002[14]")](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192012029377.png) ， [![clip_image002[10]](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/5830ff47f8743bc1ec107f4666226ffb_104x42.png "clip_image002[10]")](http://images.cnblogs.com/cnblogs_com/zabery/201107/201107192012055392.png)则 g(n) = O(n2) , f(n) = O(n2) #### **o* 记号* *O* 记号提供的渐近上界可能是也可能不是渐近紧确的。这里用 *o* 记号表示非渐近紧确的上界。 *o* ( *g* ( *n* ))的形式定义为集合：  *O* 记号与 *o* 记号的主要区别在于对 *f* ( *n* ) = *O* ( *g* ( *n* ))，界0 <= *f* ( *n* ) <= *c g* ( *n* )对某个常数 *c* > 0成立；但对 *f* ( *n* ) = *o* ( *g* ( *n* ))，界0 <= *f* ( *n* ) <= *c g* ( *n* )对所有常数 *c* > 0都成立。即  #### **Ω* 记号* *Ω* 记号给出了函数的渐近下界。给定一个函数 *g* ( *n* )，用 *Ω* ( *g* ( *n* ))表示一个函数集合：  上图说明了 *Ω* 记号的直观意义。对所有在 *n0* 右边的 *n* 值，函数 *f* ( *n* )的数值等于或大于 *c g* ( *n* )。 **定理**  对任意两个函数 *f* ( *n* )和 *g* ( *n* )， *f* ( *n* ) = *Θ* ( *g* ( *n* ))当且仅当 *f* ( *n* ) = *O* ( *n* )和 *f* ( *n* ) = *Ω* ( *g* ( *n* ))。 #### *ω* 记号 我们用 *ω* 记号来表示非渐近紧确的下界。 *ω* ( *g* ( *n* ))的形式定义为集合：  关系 *f* ( *n* ) = *ω* ( *g* ( *n* ))意味着  如果这个极限存在。也就是说当 *n* 趋于无穷时， *f* ( *n* )相对 *g* ( *n* )来说变得任意大了。 #### 函数间的比较 设 *f* ( *n* )和 *g* ( *n* )是渐近正值函数。 **传递性：** - *f* ( *n* ) = *Θ* ( *g* ( *n* ))和 *g* ( *n* ) = *Θ* ( *h* ( *n* )) 蕴含 *f* ( *n* ) = *Θ* ( *h* ( *n* )) - *f* ( *n* ) = *O* ( *g* ( *n* ))和 *g* ( *n* ) = *O* ( *h* ( *n* )) 蕴含 *f* ( *n* ) = *O* ( *h* ( *n* )) - *f* ( *n* ) = *Ω* ( *g* ( *n* ))和 *g* ( *n* ) = *Ω* ( *h* ( *n* )) 蕴含 *f* ( *n* ) = *Ω* ( *h* ( *n* )) - *f* ( *n* ) = *o* ( *g* ( *n* ))和 *g* ( *n* ) = *o* ( *h* ( *n* )) 蕴含 *f* ( *n* ) = *o* ( *h* ( *n* )) - *f* ( *n* ) = *ω* ( *g* ( *n* ))和 *g* ( *n* ) = *ω* ( *h* ( *n* )) 蕴含 *f* ( *n* ) = *ω* ( *h* ( *n* )) **自反性：** - *f* ( *n* ) = *Θ* ( *f* ( *n* )) - *f* ( *n* ) = *O* ( *f* ( *n* )) - *f* ( *n* ) = *Ω* ( *f* ( *n* )) **对称性：** - *f* ( *n* ) = *Θ* ( *g* ( *n* ))当且仅当 *g* ( *n* ) = *Θ* ( *f* ( *n* )) **转置对称性：** - *f* ( *n* ) = *O* ( *g* ( *n* ))当且仅当 *g* ( *n* ) = *Ω* ( *f* ( *n* )) - *f* ( *n* ) = *o* ( *g* ( *n* ))当且仅当 *g* ( *n* ) = *ω* ( *f* ( *n* )) ### 求解递归式的方法。 #### 递归树法 递归树法是一种解递归式比较特别的方法，在第一节将归并排序的时候有用到过这个方法。它最棒的一点就是总是能用，它能告诉你一种直觉让你知道答案是多少，只是有些不严谨。所以用这个方法时要特别小心，不然可能会得到错的答案。因为它需要用到点、点、点，使用省略号来得到结论。  #### 主定理方法 主定理方法本质上可以认为是递归树方法的一个应用，但是它更精确。不同于递归树方法有省略号有待证明，主定理方法基于一个定理（主定理）。遗憾的是，主方法限制颇多只能应用到特定的递归式上。主方法是计算时间复杂度的时候用的  那么这里我在取一个不满足主定理的例子~  所以主定理不满足时就利用决策树进行带入吧！如果数学计算能力比较强大还是可以计算出来的，毕竟主定理都是决策树证明的，数学能力不强表示证明有点困难... 不过这里有个偷懒的证明方法，直接假设f（n）是一个nk形式的； T（n）=aT（n/b）+nk T（n/b）=aT（n/b2）+（n/b）k ... 所以T(n)=a（aT（n/b2）+（n/b）k）+nk=nk（1+a/bk+...+(a/bk)h)=(nk-nlogba)/(1-a/bk),接下来讨论a和bk的关系决定了为nk还是nlogba，上面如果为1则为nklogbn了。 简单的证明， 替换法举一个例子如下：  关于[程序算法艺术与实践](http://blog.csdn.net/column/details/tac-programalgrithm.html)更多讨论与交流，敬请关注本博客和新浪微博[songzi_tea](http://weibo.com/songzitea).