Когда силы врага раздроблены на небольшие группы, его проще победить. Цезарь и Наполеон управляли Европой, разделяя и завоевывая своих врагов. При помощи той же стратегии вы можете решать задачи — в особенности задачи с оптимальной подструктурой, то есть такие, которые легко делятся на подобные, но меньшие подзадачи. Их можно дробить снова и снова, пока подзадачи не станут простыми. Затем их решения объединяются — так вы получаете решение исходной задачи.
Разделить и отсортировать
Если у нас есть большой список, который нужно отсортировать, мы можем разделить его пополам: каждая половина становится подзадачей сортировки. Затем решения подзадач (то есть отсортированные половины списка) можно объединить в конечное решение при помощи алгоритма слияния[37]. Но как отсортировать эти две половины? Их тоже можно разбить на подзадачи, отсортировать и объединить.
Новые подзадачи будут также разбиты, отсортированы и объединены. Процесс разделения продолжаем, пока не достигнем базового случая: списка из одного элемента. Такой список уже отсортирован!
Этот изящный рекурсивный алгоритм называется сортировкой слиянием. Как и для последовательности Фибоначчи (см. раздел «Рекурсия»), дерево рекурсивных вызовов помогает увидеть, сколько раз функция merge_sort вызывает саму себя (рис. 3.11).
function merge_sort(list)
····if list.length = 1
········return list
····left ← list.first_half
····right ← list.last_half
····return merge(merge_sort(left),
·················merge_sort(right))
Теперь давайте найдем временную сложность сортировки слиянием. Для этого сначала подсчитаем операции, выполняемые на каждом отдельном шаге разбиения, а затем — общее количество шагов.
Подсчет операций. Допустим, у нас есть большой список размером n. При вызове функция merge_sort выполняет следующие операции:
• разбивает список на половины, что не зависит от размера списка O(1);
• вызывает функцию merge (из раздела «Итерация» мы знаем, что merge имеет сложность O(n);
• делает два рекурсивных вызова merge_sort, которые не учитываются[38].
Поскольку мы оставляем только доминирующий член и не учитываем рекурсивные вызовы, временная сложность функции составляет O(n). Теперь подсчитаем временную сложность каждого шага разбиения.
Шаг разбиения 1. Функция merge_sort вызывается для списка из n элементов. Временная сложность этого шага составляет O(n).
Рис. 3.11. Демонстрация сортировки слиянием. Прямоугольники показывают отдельные вызовы merge_sort, при этом входные данные находятся вверху, а выходные — внизу
Шаг разбиения 2. Функция merge_sort вызывается дважды, каждый раз для элементов. Мы получаем .
Шаг разбиения 3. Функция merge_sort вызывается четыре раза, каждый раз для элементов: .
.
.
.
.
Шаг разбиения x. Функция merge_sort вызывается 2x раз, каждый для списка из элементов: .
Все шаги разбиения имеют одинаковую сложность O(n). Временная сложность сортировки слиянием, следовательно, составляет x × O(n), где x — это количество шагов разбиения, необходимых для полного выполнения алгоритма[39].
Подсчет шагов. Как вычислить x? Мы знаем, что рекурсивные функции заканчивают вызывать себя, как только достигают своего базового случая. Наш базовый случай — это одноэлементный список. Мы также увидели, что шаг разбиения x работает на списках из элементов. Потому:
Если вы не знакомы с функцией log2, то не робейте! x = log2n — это просто еще один способ написать 2x = n. Программисты любят логарифмический рост.
Посмотрите, как медленно растет количество требуемых шагов разбиения[40] с увеличением общего числа сортируемых элементов (табл. 3.1).
Таблица 3.1. Количество шагов разбиения, требуемых для списков разных размеровРазмер списка (n) log2n Требуемое количество шагов разбиения 10 3,32 4 100 6,64 7 1024 10,00 10 1 000 000 19,93 20 1 000 000 000 29,89 30
Временная сложность сортировки слиянием, следовательно, составляет log2n × O(n) = O(n log n). Это колоссальное улучшение по сравнению с сортировкой выбором O(n2). Помните разницу в производительности между линейно-логарифмическими и квадратичными алгоритмами, которые мы видели в предыдущей главе на рис. 2.4? Даже если предположить, что алгоритм O(n2) будет обрабатываться быстрым компьютером, в конечном счете он все равно окажется медленнее, чем алгоритм O(n log n) на слабой машине (табл. 3.2).
Убедитесь сами: напишите алгоритмы сортировки с линейно-логарифмической и квадратичной сложностью, а затем сравните их эффективность на примере случайных списков разного размера. Когда объемы входных данных огромны, такие улучшения часто оказываются необходимы.
А теперь давайте разделим и осилим задачи, в отношении которых мы раньше применяли полный перебор.
Таблица 3.2. В случае больших объемов входных данных алгоритмы O(n log n) выполняются намного быстрее алгоритмов O(n2), запущенных на компьютерах, в 1000 раз более производительныхОбъем данных Квадратичный Логлинейный 196 (число стран в мире) 38 мс 2 с 44 000 (число аэропортов в мире) 32 минуты 12 минут 171 000 (число слов в словаре английского языка) 8 часов 51 минута 1 млн (число жителей Гавайев) 12 дней 6 часов 19 млн (число жителей штата Флорида) 11 лет 6 дней 130 млн (число книг, опубликованных за все время) 500 лет 41 день 4,7 млрд (число страниц в Интернете) 700 000 лет 5 лет
Разделить и заключить сделку
Для задачи о самой лучшей сделке (см. раздел «Полный перебор» ) подход «Разделяй и властвуй» оказывается лучше, чем решение «в лоб». Разделение списка цен пополам приводит к двум подзадачам: нужно найти лучшую сделку в первой половине и лучшую сделку во второй. После этого мы получим один из трех вариантов:
1) лучшая сделка с покупкой и продажей в первой половине;
2) лучшая сделка с покупкой и продажей во второй половине;
3) лучшая сделка с покупкой в первой половине и продажей во второй.
Рис. 3.12. Демонстрация выполнения функции trade. Прямоугольники показывают отдельные вызовы trade с входными и выходными данными
Первые два случая — это решения подзадач. Третий легко находится: нужно найти самую низкую цену в первой половине списка и самую высокую во второй. Если на входе данные всего за один день, то единственным вариантом становится покупка и продажа в этот день, что приводит к нулевой прибыли.
function trade(prices)
····if prices.length = 1
········return 0
····former ← prices.first_half
····latter ← prices.last_half
····case3 ← max(latter) — min(former)
····return max(trade(former), trade(latter), case3)
Функция trade выполняет тривиальное сравнение, разбивает список пополам и находит максимум и минимум в его половинах. Поиск максимума или минимума в списке из n элементов требует просмотра всех n элементов, таким образом, отдельный вызов trade стоит O(n).
Вы наверняка заметите, что дерево рекурсивных вызовов функции trade (рис. 3.12) очень похоже на такое же для сортировки слиянием (рис. 3.11). Оно тоже имеет log2n шагов разбиения, каждый стоимостью O(n). Следовательно, функция trade тоже имеет сложность O(n log n) — это огромный шаг вперед по сравнению со сложностью O(n2) предыдущего подхода, основанного на полном переборе.
Разделить и упаковать
Задачу о рюкзаке (см. раздел «Полный перебор» ) тоже можно разделить и тем самым решить. Если вы не забыли, у нас n предметов на выбор. Мы обозначим свойство каждого из них следующим образом:
• wi — это вес i-го предмета;
• vi — это стоимость i-го предмета.
Индекс i предмета может быть любым числом от 1 до n. Максимальный доход для вместимости c рюкзака с уже выбранными n предметами составляет K(n, c). Если рассматривается дополнительный предмет i = n + 1, то он либо повысит, либо не повысит максимально возможный доход, который становится равным большему из двух значений.
1. K(n, c) — если дополнительный предмет не выбран.
2. K(n, c − wn+1) + vn+1 — если дополнительный предмет выбран.
Случай 1 предполагает отбраковку нового предмета, случай 2 — включение его в набор и размещение среди выбранных ранее вещей, обеспечивая для него достаточное пространство. Это значит, что мы можем определить решение для n предметов как максимум частных решений для n — 1 предметов:
K(n, c) = max (K(n − 1, c),
K(n − 1, c − wn) + vn).
Вы уже достаточно знаете и должны легко преобразовать эту рекурсивную формулу в рекурсивный алгоритм. Рисунок 3.13 иллюстрирует, как рекурсивный процесс решает задачу. На схеме выделены одинаковые варианты — они представляют идентичные подзадачи, вычисляемые более одного раза. Далее мы узнаем, как предотвратить такие повторные вычисления и повысить производительность.
Рис. 3.13. Решение задачи о рюкзаке с 5 предметами и вместимостью рюкзака 4. Предметы под номерами 5 и 4 весят две единицы, остальные — одну единицу
3.7. Динамическое программирование