频道栏目
读书频道 > 软件开发 > 其他综合 > 算法之道(第2版)
2.6 O、Ω、Θ表示
2012-11-03 09:57:38     我来说两句
收藏   我要投稿

本文所属图书 > 算法之道(第2版)

本书追求的目标是算法背后的逻辑,是一本启示书,而不是一本包罗万象的算法大全。因此,本书甄选了那些最能展现算法思想、战略和精华,并能够有效训练算法思维的内容。本书将算法的讨论分为五篇:算法基础篇、算...  立即去当当网订购

对于任何数学函数,这三个记号可以用来度量其“渐近表现”,即当趋于无穷大时的阶的情况,这是算法分析中非常重要的概念。大家可以把它们分别想象成≤、≥和,分别估计了函数的渐近上界、渐近下界和准确界。诚然,渐近关系和确切大小关系是有区别的,但当问题规模很大时,忽略这种区别能大大降低算法分析的难度。

下面我们就来具体定义这三种记号的表示。

设函数f ( n )代表某一算法在输入大小为n的情况下的工作量(效率),则在n趋向很大的时候,我们将f (n)与另一行为已知的函数g(n)进行比较:

1)如果=0,则称f (n)在数量级上严格小于g(n),记为f (n)=o( g(n))。

2)如果,则称f (n)在数量级上严格大于g(n),记为f (n)=( ( g(n))。

3)如果=c,这里c为非0常数,则称f (n)在数量级上等于g(n),即f (n)和g(n)是同一个数量级的函数,记为:f (n)=Θ( g(n))。

4)如果f (n)在数量级上小于或等于g(n),则记为f (n)=O( g(n))。

5)如果f(n)在数量级上大于或等于g(n),则记为f (n)=Ω( g(n))。

这里我们假定f (n),g (n)是非负单调的,且极限存在。如果这个极限不存在,则无法对f (n)和g (n)进行比较。在进行此种计算时,一个经常用到的技术是洛必达(L'Hopital)法则。该法则由17世纪法国数学家Guillaume de L'Hopital发现(也有人认为是瑞士数学家Johann Bernoulli发现的)。该法则声称,两个函数的比率极限等于两个函数的导数的比率极限,这里当然假定两个函数的导数比率的极限存在,即有:


 

有了这个定义,就可以对素性测试的两个算法进行比较了。

,符合第1个定义,因此这两个素性测试算法的效率差异是数量级的差异。

在算法分析中,最常选取的g(n)有如下一些,见表2-1。



 

一个值得提醒的问题是,根据定义,对于任意一个g (n)函数来说,可能存在很多个函数f (n),使得f (n)=O(g(n)),即O(g(n))表示的实际上是一个函数的集合,这里的等于也不是普通意义上的等于,而是说明f (n)是函数集合o(g(n))里的一员,即f (n)=O(g(n))并不意味着f (n)等于O(g(n))。等于号的这种使用令那些严谨的科学家非常不快甚至愤怒,但计算机界人士很喜欢这种马虎的表示。不过,我们在心里应该知道,f (n)=O(g(n))并不意味着f (n)≠O(g(n))。不然,我们就被自己骗了!

等号在其他渐近表示中的使用也可以同样解释。

您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力  
上一篇:2.5 渐近分析
下一篇:2.7 最好、最坏、平均
相关文章
图文推荐
排行
热门
最新书评
特别推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站