計算時間および停止性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/06/13 18:33 UTC 版)
すべての要素が互いに異なる場合、時間計算量はO(n×n!)となる（1回の並べ直しに必要な操作量が n 、それを繰り返す回数の期待値のオーダーが n! ）。n! は、全ての並びのうち、正しい並びである割合である 1 / n! の逆数であり、等しい要素が含まれている場合、それによる正しい並びの個数が a とすると、O(n×n! / a) となる。以上はかなりおおざっぱな議論で、たとえば並びを判定する計算量を考慮していない。 理論的にはまた、このアルゴリズムの停止性は無限の猿定理に依ることになる。なお実際的には、現実のコンピュータで実施した場合、擬似乱数のせいで停止しないこともあり得る。
※この「計算時間および停止性」の解説は、「ボゴソート」の解説の一部です。
「計算時間および停止性」を含む「ボゴソート」の記事については、「ボゴソート」の概要を参照ください。
ウィキペディア小見出し辞書の「計算時間および停止性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 計算時間および停止性のページへのリンク
