Мастер-теорема — различия между версиями
Timur (обсуждение | вклад) |
Timur (обсуждение | вклад) |
||
Строка 79: | Строка 79: | ||
− | == | + | == Приложение к известным алгоритмам == |
{| class="wikitable" | {| class="wikitable" | ||
|- | |- | ||
Строка 102: | Строка 102: | ||
| По мастер-теореме <math>c = \log_b a</math>, where <math>a = 2, b = 2, c = 1</math> | | По мастер-теореме <math>c = \log_b a</math>, where <math>a = 2, b = 2, c = 1</math> | ||
|} | |} | ||
+ | |||
+ | == Cсылки == | ||
+ | * [http://en.wikipedia.org/wiki/Master_theorem Википедия — Мастер-теорема] | ||
+ | * [https://math.dartmouth.edu/archive/m19w03/public_html/Section5-2.pdf] | ||
+ | |||
+ | == Литература == | ||
+ | *''Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К.'' Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4 | ||
+ | |||
+ | ==См. также== | ||
+ | * [[Амортизационный анализ]] | ||
+ | |||
+ | [[Категория:Дискретная математика и алгоритмы]] | ||
+ | [[Категория:Амортизационный анализ]] |
Версия 00:33, 6 мая 2015
Мастер теорема — теорема позволяющая найти асимптотическое решение (с помощью О - большое нотации) рекуррентных соотношений, которые могут возникнуть во многих алгоритмах, например таких как разделяй и властвуй. Однако не все рекуррентные соотношения могут быть решены через мастер теорему, ее обобщения включаются в метод Акра-Бацци.
Содержание
Формулировка и доказательство мастер-теоремы
Теорема: |
Пусть у нас дано соотношение вида:
, где — количество подзадач, на которые мы разбили нашу задачу, — размер нашей задачи, — размер подзадачи, — стоимость работы, проделанной рекурсивными вызовами, который включает в себя стоимость деления проблемы и стоимость слияния решения подзадач, — единичная стоимость для данной задачи. Пусть — число большее 1, — число большее 1, пусть также — число и — , тогда возможны три случая: 1. Если , то2. Если 3. Если , то , то |
Доказательство: |
Для доказательства мы установим , это требуется для того, чтобы наши вычисления были хорошо определены при рекурсивном спуске. Давайте рассмотрим дерево рекурсии. Всего в нем будет уровней. На каждом таком уровне, количество подзадач будет умножаться на , так на уровне будет подзадач. Также известно, что каждая подзадача на уровне размера . Подзадача размера требует дополнительных затрат, поэтому общее количество совершенных операций на уровне : Заметим, что количество занятой памяти увеличивается, уменьшается и остается константой, если увеличивается, уменьшается или остается константой соответственно. Поэтому мы должны разобрать три случая, когда больше 1, равен 1 или меньше 1. Рассмотрим . Распишем всю работу в течение рекурсивного спуска: Откуда получаем:1. (т.к. убывающая геометрическая прогрессия)2. 3. , но |
Примеры
1.Пусть у нас задано такое рекуррентное соотношение:
Рассчитать для
.
Заметим, чтобы узнать
, мы должны знать , чтобы узнать , мы должны узнать , , тогда , , тогда
2. Задано такое соотношение:
, а также
Недопустимые соотношения
Рассмотрим пару ошибочно-составленных соотношений:
- a не является константой; количество подзадач может меняться
- не полиномиальное различие f(n) и
- a<1 не может быть меньше одной подзадачи
- f(n) не положительна
- регулярно меняющееся f(n)
Приложение к известным алгоритмам
Алгоритм | Рекуррентное соотношение | Время работы | Комментарий |
---|---|---|---|
Целочисленный двоичный поиск | По мастер-теореме | , где||
Обход бинарного дерева | По мастер-теореме | where||
Сортировка слиянием | По мастер-теореме | , where
Cсылки
Литература
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е издание. М.: Издательский дом "Вильямс", 2005. ISBN 5-8459-0857-4