sorting - 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(无穷大) ，因为试图对无限功能。)

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

Answer 1

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

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

希望这有帮助!