algorithm - for i : for o = i+1 的复杂度是多少

Question

for i = 0 to size(arr)
   for o = i + 1 to size(arr)
      do stuff here

这个的最坏时间复杂度是多少？不是N^2，因为第二个每i个循环减一。不是N，应该大一点。 N-1 + N-2 + N-3 + ... + N-N+1。

Answer 1

它是 N ^ 2，因为它是两个线性复杂度的乘积。

(渐近复杂性被称为渐近而不是相同是有原因的...)

参见 Wikipedia's explanation on the simplifications made .