Изменения

Перейти к: навигация, поиск

Быстрая сортировка

66 байт добавлено, 20:32, 15 июня 2011
Нет описания правки
{{В разработке}}
'''Быстрая сортировка'''(qsort, сортировка Хоара) - один из самых известных и широко используемых алгоритмов сортировки. В худшем случае работает за <Tex>O(n^2)</Tex>, среднее Среднее время работы <Tex>O(nlogn)</Tex>, что является асимптотически оптимальным временем работы для алгоритма, основанного на сравнении.
==Алгоритм==
==Асимптотика==
Oh, boy, here we go!
===Худшее время работы===
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение
http://en.wikipedia.org/wiki/Quicksort
 
==Литература==
* Т. Кормен, Ч. Лейзерсон, Р. Ривест: Алгоритмы: построение и анализ глава 7
76
правок

Навигация