算法(4th ed)(165):基础——算法分析 6.4.7

阅读数:32 2019 年 11 月 6 日 07:59

算法(4th ed)(165):基础——算法分析 6.4.7

(增长数量级的分类:指数级别)

在第 6 章中(也只会在第 6 章)我们将会遇到运行时间和 2N 或者更高级别的函数成正比的程序。一般我们会使用指数级别来描述增长数量级为 bN 的算法,其中 b>1 且为常数,尽管不同的 b 值得到的运行时间可能完全不同。指数级别的算法非常慢——不可能用它们解决大规模的问题。但指数级别的算法仍然在算法理论中有着重要的地位,因为它们看起来仍然是解决许多问题的最佳方案。

以上是最常见分类,但肯定不是最全面的。算法的增长数量级可能是 N2logN 或者 N3/2 或者是其他类似的函数。实际上,详细的算法分析可能会用到若干个世纪以来发明的各种数学工具。

我们所学习的一大部分算法的性能特点都很简单,可以使用我们所讨论过的某种增长数量级函数精确地描述。因此,我们可以在某个成本模型下提出十分准确的命题。例如,归并排序所需的比较次数在 1/2NlgNNlgN 之间,由此我们立即可知归并排序所需的运行时间的增长数量级是线性对数的。简单起见,我们将这句话简写为归并排序是线性对数的

图 1.4.5 显示了增长数量级函数在实际应用中的重要性。其中 x 轴为问题规模,y 轴为运行时间。这些图表清晰的说明了平方级别和立方级别的算法对于大规模的问题是不可用的。许多重要的问题的直观解法是平方级别的,但我们也发现了它们的线性对数级别的算法。此类算法(包括归并排序)在实践中非常重要,因为它们能够解决的问题规模远大于平方级别的解法能够处理的规模。因此,在本书中我们自然希望为各种基础问题找到对数级别、线性级别或是线性对数级别的算法。

算法(4th ed)(165):基础——算法分析 6.4.7

图 1.4.5 典型的增长数量级函数

评论

发布