Главная » Java, Структуры данных и алгоритмы » Сортировка методом слияния и рекуррентные соотношения

0

Существует еще один способ обоснования утверждения 10.3, гласящего, что время выполнения алгоритма сортировки равно О(п log п), в основу которого положена рекурсивная природа алгоритма сортировки методом слияния. В этом разделе содержится именно такой анализ алгоритма сортировки, и по этой причине представляется математическая концепция рекуррентных отношений (recurrence relation).

Пусть функция t(n) соответствует максимальному времени выполнения сортировки методом слияния исходной последовательности размером п. Поскольку сортировка методом слияния рекурсивна, можно охарактеризовать функцию t(n) с помощью следующих уравнений:

точно и верно, тем не менее требуется определить функцию t(n), явно не привлекая для этого ее саму (то есть требуется замкнутая (аналитическая) характеристика t(n) (closed-form characterization)).

Повторив еще раз, получим

Теперь следует решить, когда остановить этот процесс. Это следует из t(n) = b при п < 1, что происходит при 2′ — п, то есть при / = log п. Сделав такую подстановку, получим

Таким образом, получено альтернативное обоснование того, что t(n) соответствует 0{п log п).

В следующем разделе покажем, как можно использовать сортировку и алгоритм merge для реализации абстрактного типа данных для множеств.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии