Слияние двух отсортированных списков

Часто алгоритмы обладают временем выполнения O(n) по более сложным причи- нам. Сейчас будет рассмотрен алгоритм слияния двух отсортированных списков, который немного выходит за рамки «однопроходной» схемы, но при этом все равно обладает линейным временем.

Допустим, имеются два списка, каждый из которых состоит из n чисел: a1, a2, ..., an и b1, b2, ..., bn. Оба списка уже отсортированы по возрастанию. Требуется объ- единить их в один список c1, c2, ..., c2n, который также упорядочен по возрастанию. Например, при слиянии списков 2, 3, 11, 19 и 4, 9, 16, 25 должен быть получен список 2, 3, 4, 9, 11, 16, 19, 25.

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

Иначе говоря, имеется следующий алгоритм:

Объединение отсортированных списков A = aг............. an и B = b1................. bn:

Создать для каждого списка текущий указатель Current, который инициализируется указателем на начальные элементы

Пока оба списка не пусты:

Присвоить a и b элементы, на которые указывают текущие указатели Присоединить меньший из этих двух элементов к выходному списку Переместить текущий указатель в списке, из которого был выбран меньший элемент

Конец Пока

Когда один из списков окажется пустым, присоединить остаток другого списка к выходному списку

Схема работы этого алгоритма изображена на рис. 2.2.

Утверждение о линейной границе времени выполнения хотелось бы подтвер- дить тем же аргументом, который использовался для алгоритма поиска максимума: «Для каждого элемента выполняется постоянный объем работы, поэтому общее время выполнения составляет O(n)».

Но на самом деле нельзя утверждать, что для каждого элемента выполняется постоянная работа. Допустим, n — четное число; рассмотрим списки A = 1, 3, 5, ..., 2n - 1 и B = n, n + 2, n + 4, ..., 3n - 2. Число b1 в на- чале списка B будет находиться в начале списка для n/2 итераций при повторном

выборе элементов из A, а следовательно, будет участвовать в Ω(n) сравнениях. Каждый элемент может быть задействован максимум в O(n) сравнениях (в худшем случае он сравнивается с каждым элементом другого списка), и при суммировании по всем элементам будет получена граница времени выполнения O(n2). Эта граница верна, но можно существенно усилить ее точность.

Рис. 2.2. Чтобы выполнить слияние двух списков, мы в цикле извлекаем меньший из начальных элементов двух списков и присоединяем его к выходному списку


Самый наглядный аргумент — ограничение количества итераций цикла «Пока» по «учетной» схеме. Предположим, для каждого элемента при выборе и добавле- нии его в выходной список взимается оплата. За каждый элемент платить придется только один раз, так как оплаченный элемент добавляется в выходной список и уже никогда не рассматривается алгоритмом. Всего существуют 2n элементов, и каждая итерация оплачивается некоторым элементом, поэтому количество итераций не может быть больше 2n. В каждой итерации используется постоян- ный объем работы, поэтому общее время выполнения имеет границу O(n), как и требовалось.

Хотя алгоритм слияния перебирает свои входные списки по порядку, «чере- дование» последовательности обработки списков требует применения чуть более сложного анализа времени выполнения. В главе 3 будут представлены алгоритмы с линейным временем для графов, которые требуют еще более сложного процесса управления: для каждого узла и ребра графа тратится постоянное время, но по- рядок обработки узлов и ребер зависит от структуры графа.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Слияние двух отсортированных списков:

  1. Номер один в списке неправильных действий
  2. Слияние с Гуру
  3. 5) Слияние с Мастером
  4. Статья 106. Слияние, присоединение, деление и преобразование юридического лица
  5. Статья 107. Порядок прекращения юридического лица путем слияния, присоединение, деления и преобразования
  6. 1. О двух путях развития
  7. Закон двух колес
  8. Закон двух колес
  9. Ссора двух подруг
  10. Метаязык двух слов.
  11. Книга состоит из двух частей.
  12. Земля после Затопления двух Континентов
  13. НЛП целиком построено на двух фундаментальных принципах:
  14. Анкета - это диалог двух заинтересованных людей
  15. Скрытый кризис: от тридцати пяти до сорока двух
  16. Для большинства людей вполне достаточно двух пятнадцатиминутных медитаций в день.
  17. Сефера: Крайон, для чего все эти существа прибыли вместе с нами из Атлантиды? Для чего слияние рас прошлого и настоящего (или будущего)?