Bogosort的平均时间复杂度是多少？

Question

我听说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）试图将约束置于a无限功能。）

谁能解决这个问题？还是没有无限和就无法书写或近似的复杂性？

Answer 1

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

如果您希望就此主题进行正式的数学阐述，请考虑阅读分析慢速方式的文章，该文章分析了Bogosort和其他相关排序。

希望这可以帮助！