1

これは非常に単純な質問ですが、概念を完全に理解するのに苦労しています。

次のステートメントの違いを理解しようとしています。

  1. 最良の場合、O(n) の n 個の数値の配列をソートするアルゴリズムが存在します。
  2. すべてのアルゴリズムは、最良の場合、O(n) の n 個の数値の配列をソートします。
  3. 最良の場合、Omega(n) で n 個の数値の配列をソートするアルゴリズムが存在します。
  4. すべてのアルゴリズムは、最良の場合、Omega(n) の n 個の数値の配列をソートします。

最初に、何が私を夢中にさせているのかを説明します。1と3についてはわかりませんが、そのうちの1つは1つのケースを指定するだけで答えが正しく、もう1つは可能なすべての入力を調べることで答えが正しいことを知っています。したがって、配列が既にソートされていることを指定するだけで、そのうちの1つが真でなければならないことはわかっていますが、どれかはわかりません。私の先生はいつも、クラスで誰が一番背が高いかを調べているように考えるように言いましたが、これらのオプション (1,3) のいずれかによって、彼がそうであると言うだけで十分であり、クラス全体を調べる理由はありません.

最悪のケースを調べた場合、これらのステートメントのどれも当てはまらないことはわかっています。なぜなら、仮定や追加のメモリを使用しない最適な並べ替えアルゴリズムOmega(nlogn)は

重要な注意:私は解決策 (一致する並べ替えを実行できるアルゴリズム) を探しているわけではありません。概念をもう少しよく理解しようとしているだけです。

ありがとうございました！

4

2 に答える 2

2

1+3 について自問してみてください - 最良のケースで配列をソートできるアルゴリズムを知っていますかTheta(n)- 答えが真の場合、両方の 1+3 が真です - Theta(n) はO(n) [intersection] Omega(n)であるため、そのようなものがある場合アルゴリズム (Theta(n) ベスト ケースで実行される) - 1+3 の両方が正しい。
ヒント: 最適化されたバブル ソート。

2 の場合: 自問してみてください - すべてのアルゴリズムがO(n)最良の場合に数値の配列をソートしますか? 最悪の場合と最良の場合の時間計算量が同じアルゴリズムを知っていますか? すべての最適化を外すと、前述のバブル ソートはどうなりますか?

4 の場合: 自問してください - 配列が確実にソートされるようにするために、すべての要素を読み取る必要がありますか? もしそうなら -Omega(n)は明確な下限であり、それよりもうまく行くことはできません。

幸運を！

于 2013-02-03T09:50:10.873 に答える
1

違いは、明らかに、「O」と「オメガ」という用語にあります。1 つは「より速く上昇しない」と言い、2 番目は「より遅くはない」と言う。

これらの用語の違いを理解していることを確認してください。そうすれば、文の違いがわかります。

1 と 3 は、2 と 4 がそうであるように、まったく別のことを述べています。

それらを見てください（それらは同じではありません！）：

1~ 10 個のアイテムに対して、最良の場合でも 30 個を超えないアルゴリズムが存在します。
3~ 10 個のアイテムに対して、最良の場合でも 30 個未満にならないアルゴリズムが存在します。

2~ 10 個のアイテムに対して、最良のケースで 30 個以下のアルゴリズムが必要です。
4~ 10 個のアイテムに対して、最良のケースで 30 個以上かかるすべてのアルゴリズム。

今、違いを感じますか？O/Omegaでも違いは似ていますが、調査対象が異なります。上記の例は、いくつかのポイント/ケースでの異なるパフォーマンスについて述べていますが、O/オメガ表記は、データのサイズに関連するパフォーマンスについて示していますが、データが「十分に大きい」場合に限ります。それは一定の要因を落とします：

function 1000000*n is O(n)
function 0.00000*n*n is O(n^2)

少量のデータの場合、2 番目の方が明らかに 1 番目よりも非常に優れています。しかし、データの量が増えると、すぐに最初のほうがはるかに良くなり始めます!

上記の例を、元の文により似た「より適切な」用語に書き直します。

1~ N 個を超えるアイテムに対して、最良のケースで X*N を超えないアルゴリズムが存在します。
3~ N 個を超えるアイテムに対して、最良のケースで X*n 未満にならないアルゴリズムが存在します。

2~ N 個を超えるアイテムに対して、最良のケースで X*N 以下のすべてのアルゴリズム。
4~ N 個を超えるアイテムに対して、最良のケースで X*N 以上かかるすべてのアルゴリズム。

この違いを「見る」「感じる」のに少しでもお役に立てれば幸いです。

于 2013-02-03T10:49:33.587 に答える