16 (1106253), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Длярезультирующих подмассивов из примера компарандызаключены в квадратные скобки:3 [3] 2 1 4;[6] 5 7.Если f(n) и g(n) – некоторые функции, то запись g(n) = Θ(f(n))означает, что найдутся такие константы c1, c2 >0 и такое n0,что для всех n ≥ n0 выполняются соотношения0 ≤ c1f(n) ≤ g(n) ≤ c2f(n).т.е.

при больших nf(n) хорошо описывает поведение g(n).17Быстрая сортировкаОценка времени выполнения алгоритма QuickSort.(1)Время выполнения цикла do-whileΘ(n), где n = right – left +1.(2)для алгоритма QuickSort максимальное (наихудшее)время выполнения Tmax(n) = Θ(n2).Наихудшее время: при каждом Partition массив длины nразбивается на подмассивы длины 1 и n – 1.(2Д)Для Tmax(n) имеет место соотношениеTmax(n) = Tmax(n – 1) + Θ(n).Очевидно, что Tmax(1) = Θ(1).Следовательно,Tmax(n) = Tmax(n – 1) + Θ(n) =nn∑ Θ( k ) = Θ( ∑ k ) =k =1(3)k =1n⋅(n – 1)/2 = Θ(n2).Если исходный массив a отсортирован в порядкеубывания, время его сортировки в порядке возрастанияс помощью алгоритма QuickSort будет Θ(n2).18Быстрая сортировкаОценка времени выполнения алгоритма QuickSort.Минимальное и среднее время выполнения алгоритмаQuickSortTmean(n) = Θ(n⋅log n)с разными константами: чем ближе разбиение наподмассивы к сбалансированному, тем константыменьше.(4Д)Доказательство использует теорему о рекуррентныхоценках [1](5)Рекуррентное соотношение для минимального(наилучшего) времени сортировки Tmin(n) имеет видTmin(n) = 2⋅Tmin(n/2) + Θ(n),так как минимальное время получается тогда, когда накаждом шаге удается выбрать компаранд, который делитмассив на два подмассива одинаковой длины n/2.Применяя ту же теорему, получаем Tmin(n) = Θ(n⋅log n).[1] Т.

Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ.М.: МЦНМО, 1999. ISBN 5-900916-37-5, с. 66 – 73.19(4)Быстрая сортировкаОценка времени выполнения алгоритма QuickSort.(6)Рекуррентное соотношение для T(n) в общем случае,когда на каждом шаге массив делится в отношенииq:(n – q), причем q равновероятно распределено между1 и n, также можно решить и установить, чтоT(n) = Θ(n⋅log n) (та же книга, с.160 – 164).20.

Характеристики

Список файлов лекций