Как объединить два списка и отсортировать их, работая в «линейное» время?

Question

У меня есть это, и оно работает:

# E. Given two lists sorted in increasing order, create and return a merged
# list of all the elements in sorted order. You may modify the passed in lists.
# Ideally, the solution should work in "linear" time, making a single
# pass of both lists.
def linear_merge(list1, list2):
  finalList = []
  for item in list1:
    finalList.append(item)
  for item in list2:
    finalList.append(item)
  finalList.sort()
  return finalList
  # +++your code here+++
  return

Но я бы очень хотел хорошо изучить этот материал.:) Что означает «линейное» время?

Answer 1

Линейное время означает, что занимаемое время ограничено некоторым неопределенным постоянным временем (в этом контексте) количеством элементов в двух списках, которые вы хотите объединить. Ваш подход не достигает этого - требуется O (n log n) времени.

Определяя, сколько времени занимает алгоритм с точки зрения размера задачи, мы игнорируем такие детали, как скорость работы машины, что в основном означает, что мы игнорируем все постоянные члены. Для этого мы используем «асимптотическое обозначение». Они в основном описывают форму кривой, которую вы бы построили на графике размера задачи в x в зависимости от времени, взятого в y. Логика заключается в том, что плохая кривая (которая быстро становится круче) всегда приводит к замедлению времени выполнения, если проблема достаточно велика. Это может быть быстрее для очень маленькой проблемы (в зависимости от констант, которые, вероятно, зависят от машины), но для небольших проблем время выполнения обычно не является большой проблемой.

«Большой O» определяет верхнюю границу времени выполнения. Существуют взаимосвязанные обозначения для среднего времени выполнения и нижних границ, но именно «большой O» привлекает все внимание.

• O (1) - постоянное время - размер проблемы не имеет значения.
• O (log n) - довольно пологая кривая - время увеличивается немного, поскольку проблема становится больше.
• O (n) - линейное время - каждое увеличение на единицу означает, что требуется примерно постоянное количество дополнительного времени. График (приблизительно) прямая линия.
• O (n log n) изгибается вверх более круто, поскольку проблема становится более сложной, но не очень сильно. Это лучшее, что может сделать алгоритм сортировки общего назначения.
• O (n в квадрате) изгибается вверх намного круче, так как задача усложняется. Это типично для более медленных алгоритмов сортировки, таких как пузырьковая сортировка.

Самые противные алгоритмы классифицируются как «np-hard» или «np-complete», где «np» означает «неполиномиальный» - кривая становится круче быстрее, чем любой полином. Экспоненциальное время это плохо, но некоторые еще хуже. Подобные вещи все еще выполняются, но только для очень маленьких проблем.

РЕДАКТИРОВАТЬ последний абзац неверен, как указано в комментарии. У меня есть некоторые дыры в моей теории алгоритмов, и, очевидно, пришло время проверить то, что я думал Я выяснил. А пока я не совсем уверен, как исправить этот абзац, поэтому просто предупреждаю.

В случае вашей проблемы слияния учтите, что ваши два входных списка уже отсортированы. Самый маленький элемент из вашего вывода должен быть наименьшим из одного из ваших входов. Получите первый элемент от обоих и сравните два, и поместите наименьшее в ваш вывод. Поместите самое большое назад, откуда оно пришло. Вы проделали постоянную работу и обработали один предмет. Повторяйте, пока оба списка не будут исчерпаны.

Некоторые детали ... Во-первых, помещать элемент обратно в список, просто чтобы вытащить его снова, явно глупо, но это облегчает объяснение. Далее - один входной список будет исчерпан раньше другого, так что вам нужно с этим справиться (в основном просто очистите остальную часть другого списка и добавьте его в вывод). Наконец, вам не нужно удалять элементы из списков ввода - опять же, это только объяснение. Вы можете просто пройти через них.

Answer 2

Линейный означает O (n) в Big O нотации , в то время как ваш код использует sort(), что наиболее вероятно O(nlogn).

Вопрос задается для стандартный алгоритм слияния .Простая реализация Python будет:

def merge(l, m):
    result = []
    i = j = 0
    total = len(l) + len(m)
    while len(result) != total:
        if len(l) == i:
            result += m[j:]
            break
        elif len(m) == j:
            result += l[i:]
            break
        elif l[i] < m[j]:
            result.append(l[i])
            i += 1
        else:
            result.append(m[j])
            j += 1
    return result

>>> merge([1,2,6,7], [1,3,5,9])
[1, 1, 2, 3, 5, 6, 7, 9]

Answer 3

Если вы построите результат в обратном порядке, вы можете использовать pop() и все равно быть O (N)
pop() с правого конца списка не требует смещения элементов, так же, как и O (1)
Перевернуть список, прежде чем мы вернем его, - O (N)

>>> def merge(l, r):
...     result = []
...     while l and r:
...         if l[-1] > r[-1]:
...             result.append(l.pop())
...         else:
...             result.append(r.pop())
...     result+=(l+r)[::-1]
...     result.reverse()
...     return result
... 
>>> merge([1,2,6,7], [1,3,5,9])
[1, 1, 2, 3, 5, 6, 7, 9]

Answer 4

Линейное время означает, что время выполнения программы пропорционально длине входа. В этом случае вход состоит из двух списков. Если списки в два раза длиннее, то программа будет работать примерно вдвое дольше. Технически, мы говорим, что алгоритм должен быть O (n) , где n - размер входа (в данном случае длина двух входов списки объединены).

Похоже, это домашнее задание, поэтому я не буду давать вам ответ. Даже если это не домашнее задание, я считаю, что вам лучше всего взять ручку и кусок бумаги, составьте два небольших примера списков, которые отсортированы, и выясните, как вы могли бы объединить эти два списка вручную. Как только вы поняли это, реализация алгоритма - это очень просто.

(Если все пойдет хорошо, вы заметите, что вам нужно перебирать каждый список только один раз, в одном направлении. Это означает, что алгоритм действительно линейный. Удачи!)

Answer 5

Этот поток содержит различные реализации алгоритма слияния линейного времени.Обратите внимание, что для практических целей вы бы использовали heapq.merge.

Answer 6

Более простая версия, для которой требуются списки одинакового размера:

def merge_sort(L1, L2):
   res = [] 
   for i in range(len(L1)):
      if(L1[i]<L2[i]):
          first = L1[i]  
          secound = L2[i] 
      else:
          first = L2[i]  
          secound = L1[i]  
      res.extend([first,secound]) 
   return res

Answer 7

Линейное время означает O (n) сложность. Вы можете прочитать кое-что об алгоритмической сложности и нотации big-O здесь: http://en.wikipedia.org/wiki/Big_O_notation. Вы должны попытаться объединить эти списки не после получения их в finalList, попытаться объединить их постепенно - добавив элемент, убедившись, что результат отсортирован, затем добавьте следующий элемент ... это должно дать вам некоторые идеи.

Answer 8

'Линейное время' означает, что время является функцией O (n) , где n - количество введенных элементов (элементов в списках).
f (n) = O (n) означает, что существуют такие константы x и y, что x * n <= f (n) <= y * n. </p>

def linear_merge(list1, list2):
  finalList = []
  i = 0
  j = 0
  while i < len(list1):
    if j < len(list2):
      if list1[i] < list2[j]:
        finalList.append(list1[i])
        i += 1
      else:
        finalList.append(list2[j])
        j += 1
    else:
      finalList.append(list1[i])
      i += 1
  while j < len(list2):
    finalList.append(list2[j])
    j += 1
  return finalList