sortedO(n) で実行されるリストが並べ替えられている場合に True を返す関数が与えられた場合、この並べ替えの実行時間をどのように説明しますか。
def sort(l):
while not sorted(l): random.shuffle(l)
シャッフルは完全にランダムであると仮定します。
これはbig-O表記で書かれますか？または、ランダムなコンポーネントを使用してアルゴリズムを分類する他の方法はありますか?
5203 次
4 に答える
8
このアルゴリズムはBogosortと呼ばれます。これは、 Las Vegas Algorithmsと呼ばれるアルゴリズムのクラスのインスタンスです。ラスベガス アルゴリズムはランダム化されたアルゴリズムであり、常に正しい結果を保証しますが、コンピューティング リソースについては保証しません。
ボゴソートの時間複雑度は、その確率論的性質のため、バッハマン・ランダウ記法で直接表現することはできません。ただし、予想される時間の複雑さについて述べることができます。Bogosort の予想される時間計算量は です。O(n·n!)
于 2008-11-14T01:56:17.170 に答える
6
信じられないかもしれませんが、これに関する wiki エントリがあります: http://en.wikipedia.org/wiki/Bogosort
平均的なケース: O(N*N!)
于 2008-11-14T01:29:20.813 に答える
3
平均的なケースは確かに O( NN!) です。
正確に N あることに注意してください! N 要素の順列。正しいものを選ぶ確率はちょうど 1/N! です。したがって、大数の強力な法則により、期待されるシャッフル数は N! です。
他の因数 N はどこから来ますか? すべてのステップで、選択した順列を確認する必要があります。これは、隣接する要素を比較することで直線的に行うことができます。したがって、余分な係数 N.
上記のコメントは、O(g(n)) 表記が「最悪のケース」であることを示しています。
1) そうではありません。O(g(n)) の定義は次のとおりです: 十分に大きな n に対して f(n) < c * g(n) + d となる c,d が存在する場合、f(n) は O(g(n)) です。 . 「最悪の場合」については何もありません。g(n) が f(n) よりも大きな関数であることはたまたまですが、純粋な数学的定義は「ケース」について何も述べていません。
2) ランダム化されたアルゴリズムの場合、とにかく「最悪のケース」の分析を行うのは無意味です。あなたは本当に悪いことになるいくつかの実行を考え出すことができます.
3) メジャー 0 のセットで本当に悪い実行が発生します (確率論者は、「ほぼ確実に」発生しないと言うでしょう)。それらを観察することは実際には不可能です。
于 2008-11-14T01:57:19.213 に答える
0
Big-O 表記は、最悪のシナリオを想定しています。最悪の場合、このアルゴリズムは決して終了しません。
于 2008-11-14T01:31:37.050 に答える