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

我听说 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) 出于挫败感，试图在无限功能。)

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

最佳答案

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

如果您想要有关此主题的正式数学说明，请考虑查看 Sorting the Slow Way 文章，其中分析了 Bogosort 和其他相关排序。

希望这可以帮助!

关于sorting - Bogosort 的平均时间复杂度是多少？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/19879556/