/*************************************************************
** 作者：P.Qingliang (P.Qingliang at msn.com)
** 创建时间： 2008-8-6
** 声明：笔记不是教程，这只是我系统学习算法的记录而已，如有错
** 误，欢迎指正。
**
*************************************************************/
检测算法的时间效率往往是在大规模的输入（n）的情况下进行，当n足够大时，研究算法的运行时间就趋向于研究算法的渐进效率了，因为我们没有必要进行过于精确的计算。在计算机中，有几种标准的方法用于简化算法的渐进分析。
渐进符号
用以表示算法的渐进时间记号是域为自然数的函数。有时域的范围可以适当的扩充以获得更广的益处。
三种渐进符号：ΘΩΟ
f(n) = Θ(g(n)) 表示的是这样的一个集合：存在c1,c2，当n>n0时，有0 < c1g(n)
（图来自《算法导论》）
它实际上是确定了一个算法的运行时间渐进上界和渐进下界。
对应的Ω用于确定算法的渐进下界（最佳运行时间），Ο用于确定算法的渐进上界（最坏运行时间）
需要注意的是，实际上运行时间并非是n的函数，对于某个特定的n来说，运行时间与具体的输入有关，当我们用渐渐符号来表示算法运行时间时，实际上是在某个特定条件约束下说明的。
方程中的渐进符号
方程中的渐进符号实际上相当于一个匿名函数f(n)，用于表示我们不关注的部分，因为我们没有必要写出我们不关心而又繁琐的某些细节部分（如低阶项）。
对于非精确上界渐进用符号o(g(n))表示，例如2n=o( ),而精确上界渐进则用符号Ο(g(n))表示，例如 .
w与Ω的关系同O与Ο。
** 作者：P.Qingliang (P.Qingliang at msn.com)
** 创建时间： 2008-8-6
** 声明：笔记不是教程，这只是我系统学习算法的记录而已，如有错
** 误，欢迎指正。
**
*************************************************************/
检测算法的时间效率往往是在大规模的输入（n）的情况下进行，当n足够大时，研究算法的运行时间就趋向于研究算法的渐进效率了，因为我们没有必要进行过于精确的计算。在计算机中，有几种标准的方法用于简化算法的渐进分析。
渐进符号
用以表示算法的渐进时间记号是域为自然数的函数。有时域的范围可以适当的扩充以获得更广的益处。
三种渐进符号：ΘΩΟ
f(n) = Θ(g(n)) 表示的是这样的一个集合：存在c1,c2，当n>n0时，有0 < c1g(n)
（图来自《算法导论》）
它实际上是确定了一个算法的运行时间渐进上界和渐进下界。
对应的Ω用于确定算法的渐进下界（最佳运行时间），Ο用于确定算法的渐进上界（最坏运行时间）
需要注意的是，实际上运行时间并非是n的函数，对于某个特定的n来说，运行时间与具体的输入有关，当我们用渐渐符号来表示算法运行时间时，实际上是在某个特定条件约束下说明的。
方程中的渐进符号
方程中的渐进符号实际上相当于一个匿名函数f(n)，用于表示我们不关注的部分，因为我们没有必要写出我们不关心而又繁琐的某些细节部分（如低阶项）。
对于非精确上界渐进用符号o(g(n))表示，例如2n=o( ),而精确上界渐进则用符号Ο(g(n))表示，例如 .
w与Ω的关系同O与Ο。
网友评论(0)：
