同步阅读进度,多语言翻译,过滤屏幕蓝光,评论分享,更多完整功能,更好读书体验,试试 阅读 ‧ 电子书库
最后一点
我们已经简化了“大O记法”的表示。例如,加法算法与输入规模呈线性,当讨论这个算法的行为时,我们认为存在一些常数c>0,对于所有的n>n0,使得t(n)≤c*n,回忆一下,t(n)是表示加法的实际运行时间。因此我们认为,加法的性能是O(n)。细心的读者会发现我们用过一个函数f(n)=c*2n,这个函数比c*n增长要迅速得多。事实上,虽然对加法算法进行精确分析得到其性能应该为O(2n),但是这样的结论提供了非常少的信息(有可能你需要用一周多的时间来计算一个5分钟的计算任务)。解释一下原因,考虑这个函数Ω(g(n)),其中,g(n)≤t(n),这个函数表示实际运行时间的下界。一个能够计算出执行时间的上界(O)和下界(Ω)的算法,通常用Θ(f(n))来表示,其中f(n)是t(n)的上界O(f(n))以及下界的渐进表示。
为了简化分析和说明,我们选择一个比较不正式(但是被广泛接受和使用)的记法O(f(n))。我们保证讨论算法行为时,没有一个f'(n)能够比我们已经使用的O(f(n))更好地分类算法。
请支持我们,让我们可以支付服务器费用。
使用微信支付打赏