Теоретический минимум по Computer Science

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 вызывается 2^x раз, каждый для списка из элементов: .

Все шаги разбиения имеют одинаковую сложность O(n). Временная сложность сортировки слиянием, следовательно, составляет x × O(n), где x — это количество шагов разбиения, необходимых для полного выполнения алгоритма[39].

Подсчет шагов. Как вычислить x? Мы знаем, что рекурсивные функции заканчивают вызывать себя, как только достигают своего базового случая. Наш базовый случай — это одноэлементный список. Мы также увидели, что шаг разбиения x работает на списках из элементов. Потому:

Если вы не знакомы с функцией log₂, то не робейте! x = log₂ n — это просто еще один способ написать 2^x = 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

Временная сложность сортировки слиянием, следовательно, составляет log₂ n × O(n) = O(n log n). Это колоссальное улучшение по сравнению с сортировкой выбором O(n²). Помните разницу в производительности между линейно-логарифмическими и квадратичными алгоритмами, которые мы видели в предыдущей главе на рис. 2.4? Даже если предположить, что алгоритм O(n²) будет обрабатываться быстрым компьютером, в конечном счете он все равно окажется медленнее, чем алгоритм O(n log n) на слабой машине (табл. 3.2).

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

А теперь давайте разделим и осилим задачи, в отношении которых мы раньше применяли полный перебор.

Таблица 3.2. В случае больших объемов входных данных алгоритмы O(n log n) выполняются намного быстрее алгоритмов O(n²), запущенных на компьютерах, в 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 лет

Разделить и заключить сделку