time-complexity - 仅将同一数组中的元素彼此比较一次的时间复杂性？

Question

我知道同一数组的嵌套for循环在O(n ^ 2)中，但是想知道将数组的每个元素与同一数组中的所有其他元素进行一次比较的复杂性是什么？假设将元素A与元素B进行比较，那么当它的元素B轮到与其他元素进行比较时，则不需要像上一步中那样与A进行比较。因此，随着每次迭代，数组变得越来越小。这仍然是O(n ^ 2)吗？

像这样的东西:

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

谢谢

Answer 1

我总是喜欢用视觉给出答案。可以将所有元素的嵌套两个for循环视为矩阵。您将按照以下数量进行计算:

n^2 - n

驻留在 O(n ^ 2)中。在视觉上，它将类似于(X代表计算):

使用您的方法，它将变成一个三角矩阵，类似于(X代表计算):

因此，您最终需要进行以下计算:

(n-1) x n/2

可以看出，它是前一个的一半，但仍驻留在 O(n ^ 2)中。