шпоры4 (1079655), страница 3

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

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

На каждом рекурсивном вызове переданный массив делится пополам, что дает оценку для d(n) =Q (1), далее рекурсивно вызываем сортировку полученных массивов половинной длины (до тех пор, пока длина массива не станет равной единице), и сливаем возвращенные отсортированные массивы за Q (n).

Тогда ожидаемая трудоемкость на сортировку составит:
fA(n )= 2 * fA( n/2 )+ Q (1)+ Q (n)

Тем самым возникает задача о получении оценки сложности функции трудоемкости, заданной в виде (9.1), для произвольных значений a и b.

Основная теорема о рекуррентных соотношениях

Теорема принадлежит Дж. Бентли, Д. Хакен и Дж. Саксу.

Теорема.Пусть a >= 1, b > 1 - константы, g(n) - функция, пусть далее: f(n)=a*f(n/b)+g(n)

Тогда:

1)Если g(n)=O(n^log _b^a-ξ),ξ>0, то f(n)=Q(n^log _b^a)
Пример:f(n) = 8f(n/2)+n², тогда f(n) = Q(n³)

2) Если g(n)=Q(n^log _b^a), то f(n)=Q(n^log _b^a *log n)
Пример: fA(n)= 2 * fA( n/2 )+ Q (n), тогда f(n) = Q(n*log n)

3)Если g(n) = Ω (n^log _b^{a + e}), e > 0, то f(n)=Q(g(n))
Пример: f(n)=2*f(n/2)+n², имеем:

n^log _b^a = n¹, и следовательно: f(n) = Q(n²)

Данная теорема является мощным средством анализа асимптотической сложности рекурсивных алгоритмов, к сожалению, она не дает возможности получить полный вид функции трудоемкости.

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

Список файлов лабораторной работы