仅将同一数组中的元素相互比较一次的时间复杂度? [英] Time Complexity of comparing the elements in the same array to each other only once?

问题描述

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

I Know that a nested for loop for the same array is in O(n^2) but was wondering what the complexity of comparing each element of an array to all others in the same array just once? Lets say element A is compared to element B, then when its element B's turn to compare to others it doesn't need to compare to A as that was done in the previous step. So with each iteration the array is getting smaller. Is this still O(n^2)?

像这样:

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

谢谢

推荐答案

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

I always prefer give an answer visually. Nested two for loops for all elements can be thought as a matrix. You will do calculations in number of:

n^2 - n

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

which resides in O(n^2). Visually, it will be something like (X's represent calculations):

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

With your approach, it will become a triangular matrix something like (X's represent calculations):

所以你最终会计算出:

(n-1) x n/2

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

As it can be seen, it is half of previous one, but still resides in O(n^2).

这篇关于仅将同一数组中的元素相互比较一次的时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！