同步阅读进度，多语言翻译，过滤屏幕蓝光，评论分享，更多完整功能，更好读书体验，试试 阅读 ‧ 电子书库
最后一点
我们已经简化了“大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))更好地分类算法。
请支持我们，让我们可以支付服务器费用。
使用微信支付打赏