算法(4th ed)(182):基础——算法分析 6.8.1

阅读数:5 2019 年 11 月 9 日 15:38

算法(4th ed)(182):基础——算法分析 6.8.1

(处理对于输入的依赖:输入模型)

一种方法是更加小心地对我们所要解决的问题所处理的输入建模。例如,我们可能会假设 ThreeSum 的所有输入均为随机 int 值。使用这种方法的困难主要有两点:

  • 输入模型可能是不切实际的;
  • 对输入的分析可能极端困难,所需的数学技巧远非一般的学生或者程序员所能掌握。

其中前者更为重要,因为计算的目的就是发现输入的性质。例如,如果我们编写了一个程序来处理基因组,我们怎样才能估计出它在处理不同的基因组时的性能呢?描述自然界中的基因组的优秀模型正是科学家们所寻找的,因此预计我们的程序在处理自然界中得到的数据时所需的运行时间实际上也是在为寻找这个模型做出贡献!第二个困难只和最重要的几个算法的数学结果有关,我们将会看到几个用简单可靠的输入模型加上经典的数学分析帮助我们预测程序性能的例子。

评论

发布