i的复杂性是什么:对于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,因为它是两个线性复杂性的产物.

(有一个原因渐近复杂度被称为渐近而不相同 ......)

请参阅维基百科对简化的解释.