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

Question

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

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

Answer 1

有时预期运行时间是指随机选择的输入的平均运行时间。但如果它是随机算法，那么通常指的是对于每个输入，与算法随机选择相关的预期运行时间。这就是这里的意思。对于 n 个项目的每个输入，随机快速排序的平均运行时间为 O(n(log n))，仅在抛硬币时取平均值。

在这种有限的意义上，预期运行时间是随机算法运行时间的一种非常可靠的衡量标准。如果您只担心算法在内部抛硬币时可能发生的最坏情况，那么为什么还要费心抛硬币呢？你还不如让他们全是头。 (在随机快速排序的情况下，会将其简化为普通快速排序。)

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

只有当你们都想在抛硬币不是不吉利的情况下快速奔跑，并且即使在抛硬币不吉利的情况下也不想跑得太慢时，考虑抛硬币的最坏情况才有意义。例如，假设您需要一个氧气供应调节器的分类算法(用于医疗患者或潜水员)。那么随机快速排序只有在你们都希望结果非常快的情况下才有意义，为了用户的方便，并且如果最坏的情况无论如何都不会让用户窒息。这是排序算法的人为场景，因为有一些非随机排序算法(如归并排序)即使平均而言也不比快速排序慢多少。对于像素数测试这样的问题，它没有那么做作，其中随机算法比非随机算法快很多。然后，您可能希望使用随机算法为其运行——同时运行非随机算法作为备份。

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