Документ взят из кэша поисковой машины. Адрес
оригинального документа
: http://sp.cs.msu.ru/courses/alg/task1.html
Дата изменения: Fri Oct 31 19:59:01 2008 Дата индексирования: Mon Oct 1 21:21:06 2012 Кодировка: koi8-r |
Quicksort(A,p,r) [1] if p < r then [2] q := Partition(A,p,r) [3] Quicksort(A,p,q) [4] Quicksort(A,q+1,r) [5] end
Покажите, что среднее время работы алгоритма равно
.
Указания. Найдите рекуррентное соотношение, описывающее
T(n). Предположите, что
,
и докажите утверждение по индукции, используя следующее неравенство:
Является ли алгоритм
стабильным? Как он должен быть
модифицирован для достижения стабильности?