algorithm - Bogo-sort 平均运行时解释

Question

有人可以详细解释一下 bogosort 的平均案例运行时间是多少吗？

算法的伪代码：

while not isInOrder(deck):
    shuffle(deck)

Answer 1

有n!排列，只有一个是正确的（假设不同的元素）。因此，从挥手的意义上说，您会期望在大约O(n!)迭代之后选择正确的答案。^* 但是每个 shuffle/check 操作都是它本身O(n)。因此O(n.n!)总体而言。

---

_{* 准确地说，您可以建模为参数p = 1/n的几何分布随机变量！. 这样一个变量的期望值是1/p = n！.}

Answer 2

执行操作的平均尝试次数与每次尝试成功的概率成反比。

有一些n!方法可以改变n元素。如果所有元素都是不同的，则只有一种方式产生排序输出。因此，排序 shuffle 的概率为1/n!，平均尝试次数为n!。

每次洗牌都需要O(n)时间（假设 Fisher-Yates 洗牌或任何同样合理的事情）。

因此，时间复杂度为O(n!*n)。