什么是对我的复杂性：对O = I + 1 [英] What's the complexity of for i: for o = i+1

问题描述

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的

What's the worst-time complexity of this? It's not N^2, because the second one decreases by one every i loop. It's not N, it should be bigger. N-1 + N-2 + N-3 + ... + N-N+1.

推荐答案

据是 N ^ 2 ，因为它是两个线性产品复杂性。

It is N ^ 2, since it's the product of two linear complexities.

（还有一个原因，渐进复杂叫做渐近而非相同 ...）

(There's a reason asymptotic complexity is called asymptotic and not identical...)

请参阅上简化维基百科的解释做出。

这篇关于什么是对我的复杂性：对O = I + 1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！