-4

私はこのコードを書きましたが、大きなO表記を見つける必要があります。O（n2）を思いついたのですが、正しいかわかりません。誰か助けてください。ありがとう

int n = array.length;

for(int i=0;i<array.length;i++){
  int c = 1;
  for(int j=i+1;j<array.length;j++)
    if (array[i]==array[j])
      c=c+1;
    if (c>(array.length/2)){
      return array[i];
    }
  }
  return 0;
}
4

2 に答える 2

0

正解です。これは O(n^2) 操作です。これは、実行する操作の数が入力配列のデータ要素数の 2 乗に比例するためです。

一致の数が配列の長さの半分を超える場合に「救済」条件があるという事実は、操作のカーディナリティも変更しません。これは、関数の制限動作であるため、依然として N 乗操作です。

これを確認する 1 つの方法は、モンテカルロ シミュレーションです。

  1. N=2 から始めて、N= 100 まで増やします。
  2. 内部ループ内に 2 番目のカウンターを追加して、内部コード ブロックにヒットした回数を知らせます
  3. バイナリ (1/0) 値のみを持つ長さ N のランダム化された配列を作成します
  4. 関数を実行し、内側のループにヒットした回数を追跡します
  5. Nの選択ごとに、シミュレーションを100回実行し、Nの選択ごとに結果を平均します
  6. 対数対数スケールで N に対する平均反復回数をプロットします。
  7. 両対数グラフの傾きが 2 の最適直線は、操作が O(N^2) であることを示します。勾配 1 は、O(N) であることを意味します。傾き 3 は O(N^3) を示します。
于 2013-02-26T23:56:22.790 に答える
0

配列内に等しい要素が 2 つないと仮定すると、O(N2) に等しいワースト ケース バブル ソートと等しくなります。ウィキブックでサンプルの並べ替えが表示される場合があります

また、バブル ソートのコストに関する情報もここで見つかる場合があります。

于 2013-02-26T23:28:30.067 に答える