Изменения

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

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

509 байт добавлено, 21:06, 7 июня 2011
Нет описания правки
==Алгоритм==
1)* Выбираем опорный элемент. 2)* Разбиваем массив таким образом, что все элементы меньшие или равные опорному будут лежать левее опроного элемента, а большие или равные правее. 3)* Рекурсивно сотрируем "маленькие" и "большие" элементы.
===Оптимизация глубины рекурсии до O(logn) в худшем случае===
Oh, boy, here we go!
===Худшее время работы===
Обозначим худшее время работы за <tex>T(n)</tex>. Получим рекуррентное соотношение
<tex>T(n) = Max(T(q-1)+T(n-q-1))+\Theta(n)</tex>
Предположим, что <tex>T(n) \leq cO(n^2)</tex>. Тогда получим
<tex>T(n) \leq Max(cq^2+c(n-q-1)^2)+\Theta(n) =
cMax(q^2+(n-q-1)^2)+\Theta(n)</tex>
<tex>Max(q^2+(n-q-1)^2) \leq (n-1)^2</tex>
 
<tex>T(n) \leq cn^2 - c(2n-1) + \Theta(n) \leq cn^2</tex>
Таким образом <tex>T(n) = O(n^2)
===Среднее время работы===
76
правок

Навигация