算法(4th ed)(183):基础——算法分析 6.8.2

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

算法(4th ed)(183):基础——算法分析 6.8.2

(处理对于输入的依赖:对最坏情况下的性能的保证)

有些应用程序要求程序对于任意输入的运行时间均小于某个指定的上限。为了提供这种性能保证,理论研究者们要从极度悲观的角度来估计算法的性能:在最坏情况下程序的运行时间是多少?例如,这种保守的做法对于运行在核反应堆、心脏起搏器或者刹车控制器之中的软件可能是十分必要的。我们希望保证此类软件能够在某个指定的时间范围内完成任务,否则结果会非常糟糕。科学家们在研究自然界时一般不会去考虑最坏的情况:在生物学中,最坏的情况也许是人类的灭绝;在物理学中,最坏的情况也许是宇宙的结束。但是在计算机系统中最坏情况是非常现实的忧虑,因为程序的输入可能来自另外一个(可能是恶意的)用户而非自然界。例如,没有使用提供性能保证算法的网站无法抵御拒绝服务攻击,这是一种黑客用大量请求淹没服务器的攻击,会使网站的运行速度相比正常状态大幅下降。因此,我们的许多算法的设计已经考虑了为性能提供保证,例如:

命题 D。在 Bag(请见算法 1.4)、Stack(请见算法 1.2)和 Queue(请见算法 1.3)的链表实现中所有的操作在最坏情况下所需的时间都是常数级别的。
证明。由代码可知,每个操作所执行的指令数量均小于一个很小的常数。注意:该论证依赖于一个(合理的)假设,即 Java 系统能够在常数时间内创建一个新的 Node 对象。

评论

发布