预计运行时间与最坏情况运行时间

Question

我正在研究随机快速排序算法.我意识到这个算法的运行时间总是表示为"预期运行时间".

指定或使用"预期运行时间"的原因是什么？我们为什么不计算最差或平均情况？

Answer 1

有时,预期的运行时间意味着随机选择的输入的平均运行时间.但是,如果它是一个随机算法,那么通常意味着对于每个输入,算法对随机选择的预期运行时间.这就是这里的意思.对于n个项目的每个输入,随机快速排序平均在时间O(n(log n))中运行,仅在其硬币翻转时平均.

在这种有限的意义上,预期的运行时间是对随机算法的运行时间的非常可靠的测量.如果您只担心算法在内部翻转硬币时可能发生的最坏情况,那么为什么还要费心翻转硬币呢？你不妨让他们全部成为头脑.(在随机快速排序的情况下,将其减少到普通快速排序.)

平均情况与最坏情况是一个更严重的问题,当它是平均超过投入而不是平均超过硬币翻转时.在这种情况下,平均运行时间充其量只是一个不适应输入类型变化的数字 - 算法的不同用途可能有不同的输入分布.我说充其量只是因为你可能不知道输入的假设分布是真正的用法.

看看关于硬币翻转的最坏情况只有当你想要在你的硬币翻转并不是不吉利时快速奔跑时才有意义,并且即使你的硬币翻转不运行也不会太慢.例如,假设您需要一个用于氧气供应的调节器的排序算法(对于医疗患者或潜水员).然后,随机化的快速排序只有在你希望结果通常非常快的时候才会有意义,为了方便用户,并且如果最坏的情况不会让用户窒息,无论如何.这是一种用于排序算法的设计方案,因为有非随机排序算法(如合并排序),即使平均也不比快速排序慢得多.这对于像素性测试,其中随机算法是一个问题,少做作远高于非随机算法快.然后,您可能希望使用随机算法运行它 - 同时运行非随机算法作为备份.

(好吧,你可能想知道为什么氧气调节器想知道特定的数字是否是主要的.也许它需要与医疗计算机网络通信,并且出于医疗隐私的原因,通信需要是安全的......)

Answer 2

当我们说“预期的运行时间”时，我们所指的是平均情况下的运行时间。我们可能在谈论渐近的上限或下限（或两者都有）。同样，我们可以渐进地讨论最佳或最差情况下运行时间的上限和下限。换句话说，边界与情况正交。

在随机快速排序的情况下，人们谈论的是预期的运行时间（O（n log n）），因为这使该算法看起来比最坏情况的O（n ^ 2）算法要好（尽管在算法中不是渐近的）最坏的情况下）。换句话说，对于几乎所有输入而言，随机快速排序比例如Bubblesort渐近快得多，人们希望有一种方法可以使这一事实变得清晰。因此，人们强调随机快速排序的平均情况运行时间，而不是事实，即在最坏情况下，它与Bubblesort一样渐近地恶化。

正如评论和格雷格（Greg）的出色答案中指出的那样，对于在固定，任意输入上执行算法期间执行的一系列随机选择序列，通常期望谈论预期的运行时间。这可能更自然，因为我们认为输入是由主动算法被动作用的。实际上，这等同于说出随机输入的平均值和执行算法时不考虑结构差异的算法。与这组输入和随机选择对的真实平均值相比，这两种表达方式都更容易直观显示，但是无论采用哪种方式，您都可以获得相同的答案。