我正在学习随机快速排序算法。我意识到这个算法的运行时间总是表示为“期望运行时间”。
为什么要指定或使用“期望运行时间”？为什么不计算最坏情况或平均情况？
预期运行时间与最坏情况运行时间
8
- minyatur
1
1请参见http://www.quora.com/What-is-the-difference-between-Average-Time-Complexity-and-Expected-Time-Complexity。 - Jim Mischel
4个回答
9
有时候，期望的运行时间是指对于随机选择的输入而言的平均运行时间。但如果它是一种随机算法，那么通常意味着相对于算法的随机选择，对每个输入所需的期望运行时间。这就是此处的意思。对于n个元素的每个输入，随机快速排序的平均运行时间仅在其硬币翻转上平均为O(n(log n))。
在这个有限的意义上，期望的运行时间是随机算法运行时间的一种非常可靠的衡量标准。如果你只担心算法内部翻转硬币时可能发生的最坏情况，那么为什么还要翻转硬币呢？不如把它们全部变成正面。 （这样，在随机快速排序的情况下，它将被简化为普通快速排序。）
平均情况与最坏情况在针对输入的平均值而非硬币翻转的平均值时，则是一个更严重的问题。在这种情况下，平均运行时间最多只是一个不能适应输入类型变化的数字。不同使用算法的用途可能具有不同的输入分布。我说最多是因为您可能不知道假设的输入分布是否真是实际使用。
仅考虑硬币翻转的最坏情况只有在您希望在硬币翻转不太倒霉时运行速度很快，而且即使硬币翻转不太倒霉时，也不会运行得太慢才有意义。例如，想象一下，您需要一个用于氧供应调节器（用于医疗患者或潜水员）的排序算法。然后，随机快速排序只有在您既想要结果通常非常快以方便用户，又想在最坏情况下无论发生什么都不会让用户窒息时才有意义。这对于排序算法来说是一个人为制造的场景，因为有非随机排序算法（如归并排序）其平均速度与快速排序相差不大。但对于像素数检测这样的问题而言，则不是人为的场景，因为随机算法比非随机算法快得多。然后，您可能需要尝试使用随机算法——同时备份一个非随机算法。
（好吧，你可能会想知道为什么氧气调节器需要知道特定的数字是否是素数。也许它需要与医疗计算机网络进行通信，并且为了医疗隐私原因，通信需要是安全的...）
在这个有限的意义上，期望的运行时间是随机算法运行时间的一种非常可靠的衡量标准。如果你只担心算法内部翻转硬币时可能发生的最坏情况，那么为什么还要翻转硬币呢？不如把它们全部变成正面。 （这样，在随机快速排序的情况下，它将被简化为普通快速排序。）
平均情况与最坏情况在针对输入的平均值而非硬币翻转的平均值时，则是一个更严重的问题。在这种情况下，平均运行时间最多只是一个不能适应输入类型变化的数字。不同使用算法的用途可能具有不同的输入分布。我说最多是因为您可能不知道假设的输入分布是否真是实际使用。
仅考虑硬币翻转的最坏情况只有在您希望在硬币翻转不太倒霉时运行速度很快，而且即使硬币翻转不太倒霉时，也不会运行得太慢才有意义。例如，想象一下，您需要一个用于氧供应调节器（用于医疗患者或潜水员）的排序算法。然后，随机快速排序只有在您既想要结果通常非常快以方便用户，又想在最坏情况下无论发生什么都不会让用户窒息时才有意义。这对于排序算法来说是一个人为制造的场景，因为有非随机排序算法（如归并排序）其平均速度与快速排序相差不大。但对于像素数检测这样的问题而言，则不是人为的场景，因为随机算法比非随机算法快得多。然后，您可能需要尝试使用随机算法——同时备份一个非随机算法。
（好吧，你可能会想知道为什么氧气调节器需要知道特定的数字是否是素数。也许它需要与医疗计算机网络进行通信，并且为了医疗隐私原因，通信需要是安全的...）
- Greg Kuperberg
7
当我们说“期望运行时间”时，我们指的是平均情况下的运行时间。我们可能在谈论渐进上限或下限（或两者都有）。同样地，我们可以谈论最好或最差情况下运行时间的渐进上限和下限。换句话说，上限与情况无关。
对于随机快速排序算法，人们谈论期望运行时间（O(n log n)），因为这使得算法比最坏情况下的O(n^2)算法更好（尽管在最坏情况下渐近复杂度不如后者）。换句话说，与几乎所有输入相比，随机快速排序在渐近意义下要比例如冒泡排序快得多，人们希望找到一种方式来清晰地表达这个事实；因此人们强调随机快速排序的平均情况下的运行时间，而不是它在最坏情况下与冒泡排序一样渐近糟糕的事实。
正如评论和Greg的优秀答案中所指出的那样，讨论期望运行时间也可能涉及到针对算法在执行固定的任意输入时所做的一系列随机选择的集合的期望运行时间。这可能更自然，因为我们认为输入被动地受到主动算法的影响。实际上，讨论随机输入的平均值和不考虑结构差异的执行算法是等价的。这两种表述比真正的输入和随机选择对的平均值更容易可视化，但无论采用哪种方式，你都会得到相同的答案。
对于随机快速排序算法，人们谈论期望运行时间（O(n log n)），因为这使得算法比最坏情况下的O(n^2)算法更好（尽管在最坏情况下渐近复杂度不如后者）。换句话说，与几乎所有输入相比，随机快速排序在渐近意义下要比例如冒泡排序快得多，人们希望找到一种方式来清晰地表达这个事实；因此人们强调随机快速排序的平均情况下的运行时间，而不是它在最坏情况下与冒泡排序一样渐近糟糕的事实。
正如评论和Greg的优秀答案中所指出的那样，讨论期望运行时间也可能涉及到针对算法在执行固定的任意输入时所做的一系列随机选择的集合的期望运行时间。这可能更自然，因为我们认为输入被动地受到主动算法的影响。实际上，讨论随机输入的平均值和不考虑结构差异的执行算法是等价的。这两种表述比真正的输入和随机选择对的平均值更容易可视化，但无论采用哪种方式，你都会得到相同的答案。
- Patrick87
4
这是否意味着即使是随机化快速排序的最坏情况时间复杂度也是O(n^2)？ - vincent mathew
1@vincentmathew 取决于你所说的最坏情况是什么意思。请参见下面Greg的答案。基本上，如果只考虑预期的硬币翻转次数，则为O(n log n)。如果考虑最坏情况下的硬币翻转次数，则为O(n^2)，而且非常丑陋。对于你来说，什么情况算是一种情况：在随机实例上进行单次执行，还是在该实例上进行多次执行的平均值？ - Patrick87
我认为这个答案不是很准确。我认为 https://dev59.com/81zUa4cB1Zd3GeqP4pVP#7898295 这个答案更准确。 - nbro
@nbro 已处理。 - Patrick87
3
如果一个算法的行为不仅由输入决定，而且还受到随机数生成器产生的值的影响，那么这个算法就是随机化算法。因此，您需要分析预期结果。
最坏情况分析只针对输入进行。
- Avi Cohen
0
有点晚了，这更像是一条长评论，但我认为这是很重要的补充。任何期望时间为T的算法都可以成为最坏情况下O(T)的算法，马尔可夫不等式告诉我们，如果期望时间为T，则至少有1/2的概率算法将在小于2T的操作次数内完成，因此我们只需运行算法，如果它需要超过2T的操作，我们就停止并重新运行，最多进行log(1/delta)次操作，将给我们一个最多为delta失败概率的时间复杂度O(T*log(1/delta))。但由于对数函数非常小，因此出于所有实际目的，这是一个具有0失败概率的O(T)算法。例如，如果我们选择delta为从可观测宇宙中随机选择2个原子是相同原子的概率，则我们得到log(1/delta)=260，因此我们可以说我们获得了具有0失败概率的O(T)。
- Tomer Wolberg
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接