これらの番号のペアをより高速にソートするアルゴリズムはどれですか？

Question

私はPythonで2つの解決策を書いています。数字のリストを取り、合計になるものを並べ替えることになっています。どちらも同じペアを返しますが、どれが効率的ですか？私が欠けているにもよりよい解決策はありPythonのカウント方法を使用すると、二長い1

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

アルゴリズムを比較するときは、時間の複雑さを比較する必要があります。時間を測定することも良いアイデアですが、入力には大きく依存しています。

---

最初のアルゴリズムがかかり：

O（N ）

のためループの二重の。

count()にはO(N)という複雑さがあることを考慮する必要があります。 forループがあり、本体にcount()が2回呼び出されます.の後に1回、if-elseステートメントの本体に1回入ります。

O（N ）

を両方のアルゴリズムが同時に複雑性を有することを意味する：その結果、時間複雑性は得た、O(N) * 2 * O(N) = 2*O(N<sup>2</sup>)あります。結果として、多くの実験を実行し、時間測定の平均を取ることによって性能を測定し、性能を反映するのに十分な大きさの入力を意味することになりました。

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）の複雑さを軽減します。基本的には1つのループがあります。

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