2

ここの大きな o 表記は何ですか? 説明をいただければ幸いです。ありがとう。

public static int[] mystery1(int[] list) {

  int[] result = new int[2 * list.length];
  for (int i = 0; i < list.length; i++) {
    result[2 * i] = list[i] / 2 + list[i] % 2;
    result[2 * i + 1] = list[i] / 2;
  }

  return result;

}
4

4 に答える 4

10

O(n)n はリストの長さです。いずれにせよ、リスト全体を 1 回確認します。

算術演算の数は次のとおりです。

  • 2n回の乗算
  • 2n加算
  • 2n分割
  • n モジュロ演算

これは、for ループを実装するための算術演算をカウントしていません。

于 2013-02-08T20:37:50.467 に答える
4

の上）

コマンドの量は、使用する制御構造 (ループ) ほど重要ではありません。関数を考慮すると、ループは 1 つしかありません。そのループは、リストの長さ (n) を反復回数として使用します。リストの長さが 2 倍になると、ループが完了するまでにかかる時間も 2 倍になります。

于 2013-02-08T20:39:04.600 に答える
1

O（n）です。forループの反復は1つしかないためです。これはアレイの長さに依存し、直線的に増加します。

于 2013-02-08T21:02:08.427 に答える
1

Big O は最悪のシナリオを表します。2 つの異なるコンピューターが操作を実行するのにかかる時間を比較することはできないため、Big O はアルゴリズムが実行する操作の数に適用されます。操作は、メソッドの呼び出しから変数の割り当てまで、何でもかまいません。

コードを調べる

 int[] result = new int[2 * list.length]; 
  for (int i = 0; i < list.length; i++) {
    result[2 * i] = list[i] / 2 + list[i] % 2; 
    result[2 * i + 1] = list[i] / 2; 
  }

  return result;

重い負荷がforループしています。時間をループするためlist.length、このメソッドの大きな O は ですO(list.length)。ただし、完全を期すために、数えることができる他の操作があります。新しい int 配列を割り当てると、それがカウントされます。配列内のインデックスをresultとして計算すると2 * i、それもカウントされます。ただし、これらの操作には一定の時間がかかるため、ループにかかる可変時間に飲み込まれてしまいます。

メモを読む必要がありますが、さまざまなレベルの複雑さ、定数、線形、対数などがあることがわかります。

于 2013-02-08T20:40:16.427 に答える