首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》最后一点

关灯直达底部

我们已经简化了“大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))更好地分类算法。