Время O n log n

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

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

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

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

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

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