3

その複雑さを Big-O 記法で表現するにはどうすればよいですか? 外側のループのインデックスに応じて 2 番目の for ループが変化するため、少し混乱しています。まだO(n^2)ですか？またはそれほど複雑ではありませんか？前もって感謝します

for (int k = 0; k<arr.length; k++){
      for (m = k; m<arr.length; m++){
           //do something
      }
}
4

3 に答える 3

5

あなたの見積もりは、進行式から得られます。

ここに画像の説明を入力

したがって、 ですO(n^2)。なぜあなたのケースは進行中ですか？n + (n-1) + ... + 1ループの合計だからです。

于 2013-11-13T09:10:39.870 に答える
3

2 番目のループの反復をすべて追加すると、1+2+3+...+n となり、これは n(n+1)/2 (n は配列の長さ) と等しくなります。つまり、n^2/2 + n/2 です。すでにご存知かもしれませんが、big-oh 表記の関連する用語は、最大の累乗の 1 つであり、係数は関係ありません。したがって、複雑さはまだ O(n^2) です。

于 2013-11-13T09:14:02.617 に答える
1

実行時間は n^2 ループの cca 半分です

  • ただし、ビッグ O 表記では、まだ O(n^2) です。
  • 一定の時間/サイクル - 操作は O(1) として表されるため
  • O((n^2)/2) -> O((n^2)/c) -> O(n^2)
  • 非公式に、O((n^2)/2) を自分の目的で使用している人がたくさんいます (より直感的で比較可能です) ... サイクル/ランタイムに近い

それが役に立てば幸い

于 2013-11-13T09:15:33.760 に答える