這2sum算法O（nlogn）是如何？

給定一個列表L和一個int c，我必須找出列表中是否有兩個元素，合計爲c（2Sum Problem）。我想出了下面的算法：這2sum算法O（nlogn）是如何？

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 log n）的，因爲排序需要爲O（n log n）的行動。「掃描」應該採取O（n）操作。怎麼會？

我認爲最壞的情況是L=[1,1,1,1,1,c,c,c,c,c]。是怎樣的運行不是n/2 * N/2，因此爲O（n ）？

來源

2017-01-15 Justin P.

您在上面討論的算法確實具有的時間複雜度爲O（n ）。事實上，沒有必要先在這裏對元素進行排序。但是，您可以實現一個更明智的方法：首先對列表進行排序，然後維護兩個指針：left和right。從rightright移動到left在你的列表和約束始終認爲a[left]+a[right] >= sum。如果你得到一擊，你回True，如果left越過right，我們知道沒有這樣的存在，我們返回False，因爲在大多數left和right執行爲O（n）步驟，時間複雜度爲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

不同的是，你沒有從遠 - 右來檢查數組中某一點，你可以簡單地啓動，你結束了先前的迭代。

來源

2017-01-15 16:37:25

所以，如果我已經檢查L [8]，L [7]和L [6] L [0]，我不需要和他們一起檢查L [1]，總和會比C大，對不對？ –

@JustinP .:事實上，如果您在支票上存款，您不必從最右邊跑到某個特定位置。您可以在上次保存* O（n^2）*因子時結束搜索。 –

您可以完全移除內部循環，使其爲O（n）。我要依靠基本的數學和hashmaps（字典）。請注意，hashmap搜索應該發生在恆定的時間O（1）

下面的代碼是用Swift編寫的，但是你可以很容易地將它翻譯成Python。注意，它返回其總和等於 '總和' 的所有元素的索引：

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 
}

來源

2017-02-01 15:32:18

這2sum算法O（nlogn）是如何？

回答

相關問題