Таблица 3.1. Количество шагов разбиения, требуемых для списков разных размеров
| Размер списка (n) |
log2 n |
Требуемое количество шагов разбиения |
| 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 |
Временная сложность сортировки слиянием, следовательно, составляет log2 n × 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). Оно тоже имеет log2 n шагов разбиения, каждый стоимостью O(n). Следовательно, функция trade тоже имеет сложность O(n log n) — это огромный шаг вперед по сравнению со сложностью O(n2) предыдущего подхода, основанного на полном переборе.
Разделить и упаковать
Задачу о рюкзаке (см. раздел «Полный перебор»
) тоже можно разделить и тем самым решить. Если вы не забыли, у нас n предметов на выбор. Мы обозначим свойство каждого из них следующим образом:
