1

私は Big O 記法にある程度精通していますが、Big O 記法の説明がよくわかりません。

int foo(int n) {
  int p = 1;        -------------->c1        x 1
  int i = 1;         ------------->c1        x 1
  while (i < n) {     ------------>c2        x n
    int j = 1; ------------------->c1        x (n - 1)
       while (j < i) { ----------->c2        x ((1/2)n^2 - (3/2)n + 2)
         p = p * j; -------------->(c1 + c3) x ((1/2)n^2 - (3/2)n + 1)
         j = j + 1; -------------->(c1 + c4) x ((1/2)n^2 - (3/2)n + 1)
      }
    i = i + 1; ------------------->(c1 + c4) x (n - 1)
  }
  return p; ---------------------->c5        x 1        
}

(c1 + 1/2*c2 + 1/2*c3 + 1/2*c4)n^2 + (-c1 - 1/2*c2 - 3/2*c3 - 1/2*c4)n + ( 2*c1 + 2*c2 + c3 + c5)

入れ子になったループと、結果の方程式の定数と低次項の削減により、このアルゴリズムが n^2 になることを理解しています。しかし、私が理解していないのは、たとえば「x」の右辺がどのように導出されるかです ((1/2)n^2 - (3/2)n + 1)。これについての洞察は非常に高く評価されます.Big O記法の核となる概念を本当に理解する必要があります. ありがとう。

アニメーション解説はこちら

4

2 に答える 2

1

サイクル while(i < n) の n-1 回の繰り返しがあります

内部サイクルは 0、1、2、3、..n-2 回実行されます - これは算術進行であり、その合計は (n-2)(n-1)/2 = (1/2) n^2 です。 - (3/2) n + 1

于 2012-04-12T15:10:34.750 に答える