哪种算法可以更快地对这些数字对进行排序？

Question

我在python中写了两个解决方案。它应该取一个数字列表并排序合计一个数字，这两个返回相同的对，但哪一个更有效？我不知道，如果使用Python的计数方法会使得第二个长

numbers = [1, 2, 4, 4, 4, 4, 5, 7, 7, 8, 8, 8, 9] 

match = [] 
for i in range(len(numbers)): 
    for j in range(len(numbers)): 
     if (i!=j): 
      if(numbers[i] + numbers[j] == sum): 
       match.append([numbers[i], numbers[j]]) 


match2 = [] 

for i in range(len(numbers)): 
    counterPart = abs(numbers[i] - sum) 

    numberOfCounterParts = numbers.count(counterPart) 

    if(numberOfCounterParts >= 1): 
     if(counterPart == numbers[i]): 
      for j in range(numbers.count(counterPart)-1): 
       match2.append([numbers[i], counterPart]) 
     else: 
      for j in range(numbers.count(counterPart)): 
       match2.append([numbers[i], counterPart]) 

幕后更多的工作是否有一个更好的解决方案，我失踪？

Answer 1

比较算法时，应该比较它们的时间复杂度。衡量时间也是一个好主意，但很大程度上依赖于输入，现在很少。

---

第一算法以：双for循环的，因为

O（N 2 ）

。

对于第二种算法，您应该考虑到count()的时间复杂度为O(N)。你有循环，并且在它的主体count()将被调用两次，一次在abs()之后，并且一次在你所进入的if-else语句的任何一个中。作为结果的时间复杂度是O(N) * 2 * O(N) = 2*O(N<sup>2</sup>)，其产生：

O（N 2 ）

这意味着，这两个算法具有相同的时间复杂度。因此，现在通过运行大量实验并计算时间测量结果的平均值以及足够大的输入来反映性能，从而衡量其性能。

Answer 2

您可以运行测试自己使用timeit模块：

t1 = timeit(setup='from __main__ import sort1, numbers', 
      stmt='sort1(numbers)', 
      number=1) 
t2 = timeit(setup='from __main__ import sort2, numbers', 
      stmt='sort2(numbers)', 
      number=1) 

print(t1) 
print(t2) 

也注意到sum是一个可变的内置，因此不是一个好的名称...

有更好的方式是算法！特别是考虑到你在列表中有重复。

---

这里是一个更快的版本只会给你的比赛，但没有比赛的多重性：

def sum_target(lst, target): 
    # make list unique 
    unique_set = set(lst) 
    unique_list = list(unique_set) 

    remainders = {number: target-number for number in unique_list} 
    print(remainders) 

    match = set() 
    for a, b in remainders.items(): 
     if a == b and lst.count(a) >= 2: 
      match.add((a, b)) 
     else: 
      if b in remainders: 
       match.add(frozenset((a, b))) 

    return match 

Answer 3

它几乎总是有用的衡量你的算法的复杂性。

这两种算法都具有O（N^2）的复杂性，因此在性能方面几乎可以互换。

您可以通过保持值 - 索引对的映射来改进算法。它会降低O（N）的复杂度，基本上你会有一个循环。

Answer 4

是的，如果您知道数据的lower_bound和upper_bound，那么可以使用更好的算法。Counting Sort这需要O(N)时间和空间是不恒定的（这取决于上限和下限的范围）。

参考Counting Sort

PS：计数排序不是基于比较的排序算法。

请参考下示例代码：

def counting_sort(numbers, k): 
    counter = [0] * (k + 1) 
    for i in numbers: 
     counter[i] += 1 

    ndx = 0 
    for i in range(len(counter)): 
     while 0 < counter[i]: 
      numbers[ndx] = i 
      ndx += 1 
      counter[i] -= 1