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

Question

谁能详细解释一下 bogosort 的平均用例运行时间是多少？

算法的伪代码:

while not isInOrder(deck):
    shuffle(deck)

Answer 1

有 n! 个排列，其中只有一个是正确的(假设元素不同)。所以在挥手的意义上，你会期望在大约 O(n!) 次迭代后选择正确的答案。^* 但是每个洗牌/检查操作本身都是 O(n)。因此 O(n.n!) 整体。

---

_{* 准确地说，您可以建模为 geometrically-distributed random variable带有参数 p = 1/n!。这种变量的预期值为 1/p = n!。}