1

我对大 O 表示法有点熟悉，但是我遇到了一个我不太明白的大 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”的 rhs 是如何得出的，例如 ((1/2)n^2 - (3/2)n + 1)。对此的任何见解将不胜感激，我真的需要了解大 O 表示法的核心概念。谢谢。

在这里查看动画解释

4

2 回答 2

1

外循环执行n-1次数：

sum(1, i=1;n-1) = n-1.

内部循环i-1为 each 执行次数i，总共：

sum(i-1, i=1;n-1)
= sum(i, i=1;n-1) - sum(1, i=1;n-1)
= (n-1)*((n-1)+1)/2 - (n-1)
= (n-1)*n/2 - n+1
= (1/2)n^2-(3/2)n+1

使用著名的欧拉公式计算从 1 到 的数字之和n：sum(i, i=1;n) = n*(n+1)/2

于 2012-04-12T15:04:53.347 回答
1

有 n-1 次循环 while(i < n)

内循环将执行 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 回答