c++ - 大 O 符号计算

Question

我一直在为下面的片段代码确定大 o 符号，给定的表达式是我试图弄清楚的一部分。我知道给定两个普通的默认 for 循环会导致 O(n^2) 但后者完全不同。这是说明。

算法

for (j = 0; j < n; j++)
{
  for (k = j; k < n; k++)
  {
  }
}

将导致表达式给定的迭代次数:

= n + (n-1) + (n-2) + (n-3) + ........ + (n - n)

• 将上述级数表达式化简为代数表达式，不求和。

• 确定代数表达式后用Big O Notation表示表现。

Answer 1

可以用这个方法(据说是高斯小时候用的)。

如果你将所有数字相加两次，你有

     1   +   2   +   3   + ... +  n
+    n   + (n-1) + (n-2) + ... +  1
—————————————————————————————————————--
   (n+1) + (n+1) + (n+1) + ... + (n+1)   = n(n+1)

因此，

1 + 2 + 3 + ... + n = n(n+1)/2

和n(n+1)/2是(n^2)/2 + n/2，所以在O(n^ 2)。