Время 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) на сортировку чисел, с по- следующим постоянным объемом работы для каждого числа в порядке перебора. Другими словами, после сортировки вся оставшаяся работа следует основному сценарию линейного времени, который рассматривался ранее.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Время O(n log n):

  1. Время сейчас такое – время мудрости пришло!
  2. 14. 4. Рабочее время и время отдыха
  3. Зарубка на носу Дай время себе, дай время ребенку
  4. Время
  5. Время
  6. Время
  7. Время
  8. Всемирное время.
  9. Местное время.
  10. 1.2.2. Время отдыха
  11. 1.2.1 Рабочее время
  12. ВРЕМЯ
  13. ВРЕМЯ РЕАКЦИИ
  14. «Время»
  15. Настоящее время.