Время O n log n

Время O(n log n) тоже встречается очень часто, и в главе 5 будет представлена одна из главных причин его распространенности: это время выполнения любого алгоритма, который разбивает входные данные на две части одинакового размера, рекурсивно обрабатывает каждую часть, а затем объединяет два решения за линейное время.

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

Так, алгоритм сортировки слиянием разбивает входной набор чисел на две части одинакового размера, рекурсивно сортирует каждую часть, а затем объединяет две отсортированные половины в один отсортированный выходной список. Только что было показано, что слияние может быть выполнено за линейное время; в главе 5 мы обсудим анализ рекурсии для получения границы O(n log n) в общем времени выполнения.

Время O(n log n) также часто встречается просто из-за того, что во многих алгоритмах самым затратным шагом является сортировка входных данных.

Допустим, имеется набор из n временных меток x1, x2, …, xn поступления копий файлов на сервер, и нам хотелось бы определить наибольший интервал между первой и последней из этих временных меток, в течение которого не поступило ни одной копии файла.

Простейшее решение этой задачи — отсортировать временные метки x1, x2, …, xn, а затем обработать их в порядке сортировки и вычислить интервалы между каждыми двумя соседними числами. Наибольший из этих интервалов дает желаемый результат.

Этот алгоритм требует времени O(n log n) на сортировку чисел, с последующим постоянным объемом работы для каждого числа в порядке перебора. Другими словами, после сортировки вся оставшаяся работа следует основному сценарию линейного времени, который рассматривался ранее.