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

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

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

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

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

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

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

указателем на начальные элементы Пока оба списка не пусты:

Присвоить  ai   и  bj   элементы,  на  которые  указывают  текущие  указатели Присоединить меньший из этих двух элементов к выходному списку Переместить текущий указатель в списке, из которого был выбран меньший элемент Конец Пока Когда  один  из  списков  окажется  пустым,  присоединить  остаток  другого  списка к выходному списку.

Утверждение о линейной границе времени выполнения хотелось бы подтвердить тем же аргументом, который использовался для алгоритма поиска максимума:

«Для каждого элемента выполняется постоянный объем работы, поэтому общее время выполнения составляет 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). Эта граница верна, но можно существенно усилить ее точность.

Самый наглядный аргумент — ограничение количества итераций цикла «Пока» по «учетной» схеме. Предположим, для каждого элемента при выборе и добавлении его в выходной список взимается оплата.

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

Хотя алгоритм слияния перебирает свои входные списки по порядку, «чередование» последовательности обработки списков требует применения чуть более сложного анализа времени выполнения.

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