时间复杂？

Question

我知道一个嵌套的for循环在同一阵列是为O（n^2），但不知道在同一阵列中只有一次的阵列中的每个元素比较所有其它的什么复杂性？比方说，元素A相对于元素B，那么当它的元素B轮到别人比较并不需要因为这是在上一步做比作。所以在每次迭代中，数组越来越小。这仍然是O（n^2）吗？

事情是这样的：

for i in xrange(len(list)-1): 
    v = list.pop(0) 
    for vi in docs: 
     merge(v,vi) 

感谢

Answer 1

我总是喜欢在视觉上给你答复。两个嵌套的所有元素的循环可以被看作是一个矩阵。你会做的计算中的数字：它驻留在为O（n^2）

n^2 - n 

。在视觉上，它会是这样的（X就代表计算）：

你们的做法，它会成为一个三角矩阵像（X就代表计算）：

所以您将以计算金额结束：

(n-1) x n/2 

因为它可以看到n，是前一半的一半，但仍然存在于O（n^2）。