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

Добавление элемента к упорядоченному массиву — весьма ресурсоёмкая операция: легко найти (бинарным поиском) то место, куда элемент этот нужно вставить, но для самой вставки часть массива нужно подвинуть. В худшем случае это требует времени, пропорционального длине массива.

Тем не менее, если требуется добавить сразу много элементов, можно (как и в случае с обычным массивом) сделать среднее время добавления элемента малочувствительным к размеру массива. Особенно просто это осуществляется, если новые элементы уже упорядочены.

Алгоритм слияния

Приведём код без каких-либо предварительных комментариев:

def merge(a,b):
    i,j = 0,0
    c = []
    
    while i < len(a) and j < len(b):
        if a[i] < b[j]: c.append(a[i]); i += 1
        else:           c.append(b[j]); j += 1

    c += a[i:]
    c += b[j:]

    return c

Нетрудно видеть, что в результирующем массиве присутствуют все элементы входных, причём в правильном порядке (если, конечно, оба входных массива были упорядочены).

Время работы этого алгоритма пропорционально размеру результата (если, конечно, считать время доступа к элементу массива не зависящим от длины массива). Получается, например, что если мы сливаем массивы одинаковых размеров, то удельное время слияния в пересчёте на один элемент перестаёт зависеть от размера сливаемых массивов.

Алгоритм сортировки

При помощи слияния нетрудно описать рекурсивный алгоритм, позволяющий достаточно быстро упорядочить произвольный массив. Опять же, приведём сперва соответствующий код:

def merge_sort(a):
    if len(a) < 2: return a[:]

    m = len(a)//2
    
    l = merge_sort(a[:m])
    r = merge_sort(a[m:])

    return merge(l,r)

Комментарий первый: a[:] во второй строчке нужно для того, чтобы выходной массив всегда отличался от входного (такие же гарантии, например, даёт встроенная в питон функция sorted).

Комментарий второй: этот алгоритм работает за конечное время и выдаёт результат упорядочивания элементов входного массива. Доказывается тривиальной индукцией по размеру входного массива.

Комментарий третий: этот алгоритм работает за время, пропорциональное n log(n), где n — размер входного массива. Доказательству этого факта посвящён следующий раздел (те, кто в это сразу верит, могут его не читать).

Анализ времени работы алгоритма сортировки

Пусть S(n) — максимально возможное время работы алгоритма сортировки на входном массиве длины n (измеренное, например, в шагах исполнителя). Для корректности определения будем считать, что для тех n, для которых нет максимума, S(n) равно бесконечности (нечто, большее любого целого числа).

Пусть M(m,n) — максимально возможное время слияния массивов длины m и n. Единственная гипотеза, которую придётся принять за аксиому — о том, что M(m,n) <= k*(m+n) для некоторого числа k.

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

Вернёмся к нашему анализу. Нетрудно заметить следующие два факта:

  1. для некоторого целого A верно S(0) <= A и S(1) <= A.
  2. для некоторого целого B верно S(n) <= S(n//2) + S(n - n//2) + k*n + B

Теперь осталось многократно применить неравенство из пункта 2 к S из правой части этого же неравенства до тех пор, пока все аргументы всех получившихся S не станут равны 0 или 1.

Общий вид такого перехода выглядит так:

S(a_1)+...+S(a_n) <= S(a_1//2)+S(a_1-a_1//2)+...+S(a_n)+S(a_n-a_n//2) + k*(a_1+a_2+...+a_n) + n*B

Поскольку у нас всегда a_1+...+a_n равно n, каждый переход добавляет к сумме n*(k+B).

Осталось заметить, что нам явно хватит log(n) + 1 переходов: это следует из (немного неочевидного) равенства (x//a)//b = x//(a*b).

Каждый переход удваивает количество S в сумме. Поэтому, после того, как в окончательной сумме мы применим S(0) <= A и S(1) <= A, мы получим

S(n) <= A * 2 ** (log(n) + 1) + (k+b)*n*(log(n) + 1)

Учитывая, что 2 ** log(n) по определению равно n, мы получаем:

S(n) <= (2*A+k+b)*n + (k+b)*n*log(n) <= 2*(A+k+b)*n*log(n)

То есть время работы алгоритма (с точностью до постоянного множителя) не больше, чем n log(n). Ровно таким же образом можно получить и аналогичную нижнюю оценку на время работы.

PS. Те, кого не устроил несколько неформальный характер вышеприведённых рассуждений, могут просто взять (полученную этими самыми рассуждениями) оценку 2*(A+k+b)*log(n) и банально доказать её по индукции.

Добавление к упорядоченному массиву большого количества элементов

Алгоритм сортировки позволяет реализовать следующий способ добавления к упорядоченному массиву элементов:

def extend(sorted_list, new_elements):
    return merge(sorted_list, merge_sort(new_elements))

При добавлении к n-элементому массиву n элементов за один раз удельное время работы в пересчёте на один элемент получается пропорциональным log(n), что на практике зачастую вполне удобоваримо.

А вот о том, что делать, если элементы добавляются по одному, рассказано в следующей главе.

В заключение

В реальных программах на python (и сходных по производительности скриптовых языках) все вышеописанные функции достаточно бесполезны: функции sorted и lambda a,b: sorted(a+b) работают существенно эффективнее написанных вручную аналогов. Тем не менее, они демонструруют полезную в целом идеологию решения задач «разделяй и властвуй»: иногда задачу можно эффективно решить, разбив её на несколько меньших подзадач, рекуррентно решив их, а затем соединив их решения в решение исходной задачи.