Как это алгоритм 2sum O (nlogn)?

Question

Учитывая список L и int c, я должен выяснить, есть ли в моем списке два элемента, которые составляют до c (проблема 2Sum). Я придумал следующий алгоритм:

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 журнал N), так как сортировка занимает O (N журнал N) действия. Предполагается, что «сканирование» принимает O (n) действия. Как идет?

Я понял, что в худшем случае будет L=[1,1,1,1,1,c,c,c,c,c]. Как время работы не n/2 * n/2, поэтому O (n)?

Answer 1

Алгоритм, который вы обсуждаете выше, действительно имеет временную сложность O (n). На самом деле здесь нет необходимости сортировать элементы. Однако вы можете реализовать более умный: сначала отсортируйте список, а затем сохраните два указателя: left и right. right перемещается из right в left над вашим списком, и ограничение всегда содержит это значение a[left]+a[right] >= sum. В случае, если вы получаете удар, вы вернетесь True, если left проходит через right, мы знаем, нет такого удара, не существует, и мы возвращаемся False, так как в большинстве left и right выполнять O (п) шагов, время сложность 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. Обратите внимание, что она возвращает индексы всех элементов, сумма которых равна 'сумме':

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 
}