algorithm - ボゴソートの平均実行時間の説明

Question

ボゴソートの平均的なケースの実行時間について、誰かが完全に説明してもらえますか？

アルゴリズムの擬似コード：

while not isInOrder(deck):
    shuffle(deck)

Answer 1

順列がありn!、そのうちの1つだけが正しい（別個の要素を想定）。O(n!)したがって、手を振るという意味では、約反復後に正しい答えを選択することが期待されます。^* ただし、各シャッフル/チェック操作はそれ自体O(n)です。したがって、O(n.n!)全体的に。

---

_{*正確には、パラメーターp = 1/nで幾何分布確率変数としてモデル化できます。。このような変数の期待値は1/p=nです。。}

Answer 2

操作の平均試行回数は、各試行が成功する確率に反比例します。

要素n!をシャッフルする方法があります。nすべての要素が異なる場合、並べ替えられた出力を生成する方法は 1 つだけです。したがって、ソート シャッフルの確率は で1/n!あり、試行の平均回数は ですn!。

各シャッフルにはO(n)時間がかかります (Fisher-Yates シャッフルまたは同等に合理的なものを想定)。

したがって、時間計算量はO(n!*n)です。