5

我听说 Bogosort 的行为没有上限。但是，我从未听过任何人谈论它的平均行为。这是一项愚蠢的任务，但不切实际的思想实验仍然是一种很好的做法，无论它们多么不切实际。

我想说每个术语是：

P(x==y)*P(x!=y)^(k-1)
    = 1/n * (1-1/n)^(k-1)
    = (n-1)^(k-1) / n^k

其中 k 为 0 或更大。我知道该系列是收敛的，因此我们可以找到复杂性的有限到有限关系（与最坏情况的行为不同，其他人出于挫败感试图将其写为 O(infinity)无限功能。）

谁能解决这个问题？或者它是一种没有无限和就无法写出或近似的复杂性？

4

1 回答 1

9

有一种更直接的方法可以做到这一点。Bogosort 通过随机排列元素并在结果排列被排序时终止。有n！数组元素的可能排列（假设它们都是不同的）并且只有其中一个被排序。因此，输入的均匀随机排列被排序的概率由 1 / n! 给出。使用概率的标准结果，这意味着，按照预期，在我们生成排序排列之前将发生的排列数是 n!。这意味着 Bogosort 的预期运行时间是 Θ(n · n!)，因为我们执行 n! 平均随机排列，每个排列都需要时间 Θ(n) 来完成（以及 Θ(n) 时间来检查）。

如果您想对该主题进行正式的数学阐述，请考虑查看文章Sorting the Slow Way，该文章分析了 Bogosort 和其他相关排序。

希望这可以帮助！

于 2013-11-10T05:09:34.987 回答