Презентация на тему: Место и значение алгоритмов в вычислительных задачах

d(n) – трудоемкость алгоритма деления задачи на подзадачи, U(n) – трудоемкость алгоритма объединения полученных решений.

Рассмотрим, например, известный алгоритм сортировки слиянием, принадлежащий Дж. Фон Нейману:

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

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

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

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

Следующая теорема принадлежит Дж. Бентли, Д. Хакен и Дж. Саксу (1980 г.).

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

f(n)=a*f(n/b)+g(n)

Тогда:

• Если g(n)=O( ), >0, то f(n)=Q( ) Пример:f(n) = 8f(n/2)+ , тогда f(n) = Q( )
• ) Если g(n)=Q( ), то f(n)=Q( *log n) Пример: fA(n)= 2 * fA( n/2 )+ Q (n), тогда f(n) = Q(n*log n)
• Если g(n) = ( ), e > 0, то f(n)=Q(g(n)) Пример: f(n)=2*f(n/2)+ , имеем:

, и следовательно: f(n) = Q( )

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

Контрольные Вопросы:

По темам :

1 Место и значение алгоритмов в вычислительных задачах

2 Функции сложности алгоритмов и их рост

3 Принцип “разделяй и влавствуй” при построении алгоритмов

Место и значение алгоритмов в вычислительных задачах

Что такое алгоритмы

Что такое Структуры данных

Какие задачи решаются с помощью алгоритмов

Какие вы знаете задачи сортировки