pattern heroPT–23LeetCode Extension

Разделяй и властвуй

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

Вариант
P23 Разделяй и властвуйСортировка слиянием · 1×

Пример задачи: отсортировать [5, 1, 8, 3, 9, 2] сортировкой слиянием.

518392
ждёт в стеке вызововтекущий вызов или элементотсортированослитый список, ещё не заполненуже слито наверх

sort([5, 1, 8, 3, 9, 2]): 6 элементов, делим

a = [5, 1, 8, 3, 9, 2]mid = –left = –right = –out = –
01/62
сначала · назад · пуск · шаг
Скорость
1function sort(a):
2 if len(a) <= 1:
3 return a
4 mid = len(a) / 2 // rounded down
5 left = sort(a[0 .. mid - 1])
6 right = sort(a[mid .. len(a) - 1])
7 return merge(left, right)
8
9function merge(left, right):
10 out = []
11 while left and right are not empty:
12 move the smaller first item to out
13 return out + left + right

← → шаг · пробел — пауза

Как узнать

вход делится на половины, которые решаются сами по себе: отсортировать список, построить дерево по массиву или по двум обходам, дерево квадрантов, быстрое возведение в степень, слияние k отсортированных списков.

Как решать такие задачи

  1. Найди такое деление, после которого куски того же вида: две половины массива, список, разрезанный посередине, четыре квадранта.
  2. Запиши базу: самый маленький кусок, на который ответ известен сразу, — часто один элемент или пустой кусок.
  3. Реши каждый кусок рекурсивным вызовом и доверься, что вызов вернёт верный ответ.
  4. Напиши объединение и посчитай его стоимость на уровне: O(n) на уровень дают O(n log n) в сумме.

Вариант: Построить дерево

То же, но строим дерево: середина отсортированного массива становится корнем, а половины — его поддеревьями. Половины равны, плюс-минус один элемент, поэтому дерево получается сбалансированным.

  1. Передавай границы индексов (lo, hi), а не копии подмассивов: тогда деление стоит O(1).
  2. Пустой диапазон lo > hi — это база: он возвращает none.
  3. Выбери элемент, который делит остальное: середину отсортированного массива, первое значение прямого обхода для дерева по двум обходам.
  4. Создай узел, построй левую часть из одной половины и правую из другой, потом верни узел.

Где встречается

  • Сортировка больших данных. Когда данные не помещаются в память, PostgreSQL сортирует их кусками, а потом сливает отсортированные куски. В EXPLAIN это видно как «external merge».
  • Звук и сигналы. Быстрое преобразование Фурье делит сигнал на чётные и нечётные отсчёты, считает каждую половину тем же способом и склеивает результат. Так работают FFTW и numpy.fft.
  • Умножение больших чисел. Python умножает очень длинные целые методом Карацубы: делит каждое число на две половины и обходится тремя умножениями половин вместо четырёх.