この2sumアルゴリズムはどのようにしてO（nlogn）ですか？

Question

リストとint cがある場合、リストに2つの要素があるかどうかを調べる必要があります。これはc（2Sumの問題）です。今、私はソートがO（nはn個のログ）アクションを実行しますので、これは、（nはn個のログ）Oで実行されることが判明

def tsum(L,c): 
    a=sorted(L) 
    b=sorted(L,reverse=True) 
    for kleineZahl in a: 
     for großeZahl in b: 
      sum=kleineZahl+großeZahl 
      if sum>c: 
       continue 
      elif sum==c: 
       return(True) 
      elif sum<c: 
       break 
return(False) 

：私は次のアルゴリズムを思い付きました。 "スキャン"は、O（n）アクションを取ると考えられています。どうして？

私は最悪のシナリオがL=[1,1,1,1,1,c,c,c,c,c]であると考えました。ランタイムはどのようにn/2 * n/2でないのですか？O（n ）？

Answer 1

上記のアルゴリズムは実際にO（n ）という時間の複雑さを持っています。実際にはここで最初に要素をソートする必要はありません。ただし、よりスマートな方法を実装することができます。最初にリストをソートし、次に2つのポインタ：leftとrightを維持します。 rightはrightからリストの上のleftに移動し、その制約は常にa[left]+a[right] >= sumを保持します。場合にはあなたがヒットを取得し、最大leftとrightはO（n）のの手順を実行するので、rightオーバーleftパスは、我々はそのようなヒットが存在しない知っていると我々はFalseを返す場合は、Trueを返し、時間の複雑さは、（Oでありますn）ですが、ソートのステップではO（n log n）になります。よりスマートなアルゴリズムは、このようです：

def tsum(L,c): 
    a=sorted(L) 
    left = 0 
    right = len(L)-1 
    while left < right: 
     right1 = right 
     while a[left]+a[right1] > c: 
      right1 -= 1 
     if a[left]+a[right1] == c: 
      return True 
     elif right1 < right: 
      right = right1+1 
     left += 1 
return False 

違いは、あなたが以前の反復を終了した場所、あなたは、単に起動することができ、あなたの配列内の特定のポイントに遠く右回転からチェックする必要がないことです。

Answer 2

内部ループを完全に削除することで、O（n）にすることができます。 私は基本的な数学とハッシュマップ（辞書）に頼るつもりです。 ハッシュマップ検索は一定時間内に行われることに注意してください。O（1）

以下のコードはSwiftで書かれていますが、Pythonに簡単に翻訳できます。それは和 '和' と等しいすべての要素のインデックスを返すこと 注：私は既にLをチェックあれば

func findTwoSum(_ array: [Int], sum: Int) -> [(Int, Int)] { 
    var result = [(Int, Int)]() 

    var diffs = Dictionary<Int, Int>() 

    for i in 0..<array.count { 
     let val = array[i] 

     // if the number is already in the dict, we've found the pair 
     // since diff + val == sum 
     let diff = sum - val 
     if let foundIndex = diffs[diff] { 
      result.append(contentsOf: [(foundIndex, i), (i, foundIndex)]) 
     } else { 
      // store the value in the dict 
      diffs[val] = i 
     }    
    } 

    return result 
}