algorithm - 预期运行时间与最坏情况运行时间

Question

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

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

Answer 1

有时，预期运行时间是指随机选择的输入的平均运行时间。但是，如果它是一个随机算法，那么通常意味着对于每个输入，该算法做出的随机选择的预期运行时间。这就是这里的意思。对于n 项的每个输入，随机快速排序平均在 O(n(log n)) 时间内运行，仅在其掷硬币时取平均值。

在这种有限的意义上，预期运行时间是随机算法运行时间的一个非常合理的衡量标准。如果您只担心算法在内部翻转硬币时可能发生的最坏情况，那么为什么还要费心翻转硬币呢？你不妨把它们都变成头。（在随机快速排序的情况下，会将其简化为普通快速排序。）

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

仅当您既想在抛硬币不倒霉时跑得快，又想在抛硬币倒霉时跑得太慢时，查看抛硬币的最坏情况才有意义。例如，假设您需要一个用于氧气供应调节器的排序算法（用于医疗患者或水肺潜水员）。然后随机快速排序只有在你们都希望结果通常非常快时才有意义，为了用户的方便，并且如果最坏的情况无论如何都不会让用户窒息。这是排序算法的人为场景，因为有非随机排序算法（如归并排序）并不比快速排序慢很多，甚至平均而言。对于像素数测试这样的问题，它不太做作，其中随机算法很多比非随机算法更快。然后你可能想用一个随机算法来运行它——同时运行一个非随机算法作为备份。

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

Answer 2

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

在随机快速排序的情况下，人们谈论预期的运行时间 (O(n log n))，因为这使得算法看起来比最坏情况的 O(n^2) 算法更好（虽然不是渐近的）最坏的情况下）。换句话说，对于几乎所有输入，随机快速排序比冒泡排序要快得多，人们想要一种方法来明确这一事实。所以人们强调随机快速排序的平均运行时间，而不是在最坏的情况下它与冒泡排序一样渐近糟糕这一事实。

正如评论和 Greg 的出色回答中所指出的那样，在算法在固定的任意输入上执行期间做出的随机选择序列集的预期运行时间也可能很常见。这可能更自然，因为我们认为输入是由主动算法被动地作用的。事实上，这相当于说随机输入的平均值和执行不考虑结构差异的算法。这两种公式都比输入和随机选择对的真实平均值更容易可视化，但是无论您采用哪种方法，您都会得到相同的答案。

Answer 3

如果算法的行为不仅取决于其输入，还取决于随机数生成器产生的值，则该算法是随机的。这就是你分析预期的原因。

最坏情况分析仅针对输入。

Answer 4

有点晚了，这更像是一个长评论，但我认为这是很重要的补充。任何具有预期时间 T 的算法都可能成为最坏情况 O(T) 算法，马尔可夫不等式告诉我们，如果预期时间为 T，那么至少有 1/2 的概率该算法将需要少于 2T 次操作，所以我们可以运行算法，如果它需要超过 2T 的操作，我们停止并重新运行它，最多执行 log(1/delta) 次将使我们最多失败的概率为 delta。所以我们得到一个时间复杂度 O(T*log(1/delta)) 和失败概率增量。但是由于 log 非常小，因此出于所有实际原因，这是一个失败概率为 0 的 O(T) 算法。