Содержание:
Мастер Теорема позволяет нам определить сложность Divide-and-Conquer алгоритмов.
Формула мастер теоремы определяет Divide-and-Conquer алгоритмы следующим образом:
, где
-
$n$ = размер входных данных -
$a$ = количество подзадач, на которое мы разделяем текущую задачу на каждом вызове рекурсии -
$b$ = коэффициент, на который уменьшается размер задачи на каждом вызове рекурсии -
$f(n)$ = сложность работы, которая совершается в теле функции для текущей подзадачи. Включает в себя сложность как разделения (divide), так и слияния результатов подзадач (conquer)
Здесь,
Определив алгоритм через рекуррентную формулу, мы можем вычислить его asymptotically tight complexity, то есть Theta-O.
Перед тем как идти дальше, заметим следующее:
- Заметим, что вызов рекуррентной функции можно представить в виде дерева вызовов
- Определить
$f(n)$ как$f(n) = n^c$ . Например,$f(n)=n=n^1$ , т.е.$c = 1$ - Заметим, что количество работы с каждым уровнем уменьшается в
$b^c$ раз. Откуда же здесь взялось$b^c$ ? Дело в том, что$f(n)$ может иметь степень и тогда количество работы уменьшается именно в$b^c$ раз. Например, пусть мы имеем такую формулу:$T(n)=T(\frac{n}{2}) + n^2$ . Если вызвать$T(8)$ , то получим такую подзадачу:$T(8)=T(8/2) + 64 = T(4/2) + 16$ . Мы видим, что количество работы$f(n)$ уменьшилось в 4 раза, то есть в$b^c$ раз - Заметим, что дерево вызовов рекуррентной формулы - это Perfect N Tree
- Заметим, что на последнем уровне дерева вызовов рекуррентной формулы будет
$a^{\log_b n}$ листьев. Сейчас поясню. Итак, вначале мы всегда имеем 1 вызов (корень дерева), а далее на каждом следующем уровне дерева появляется в$a$ больше вызовов, чем на предыдущем. Понятно, что на последнем уровне дерева будет ровно$a^h$ листьев, где$h$ это высота дерева, которую можно определить как$h=\log_b n$ . Например, это известно, что для binary tree на последнем уровне дерева будет$2^{\log_2 n}$ листьев, где$a=b=2$ . Эта формула является всего лишь обобщением этого факта для N-Tree.
Теперь нам нужно сравнить
-
$a > b^c$ ,$T(n)=O(n^{\log_b a})$ . С каждым уровнем дерева вызовов количество рекурсивных вызовов растет быстрее, чем уменьшается размер работы, то есть сложность решения подзадач на каждом уровне увеличивается, поэтому асимптотически общая работа определяется работой на последнем уровне дерева. А последний уровень, уровень листьев, это базовый случай рекурсии, который занимает константное время, что сводит работу на этом уровне к количеству элементов на нем. Но откуда же здесь взялась такая странная формула$n^{\log_b a}$ ? Эта формула - это просто преобразование формулы количества элементов на последнем уровне, которую я дал выше, просто у нас это преобразовано к другому виду, чтобы дать оценку от$n$ в классическом виде:$a^{\log_b n} \iff n^{\log_b a}$ . -
$a = b^c$ ,$T(n)=O(f(n) * \log n)$ . С каждым уровнем дерева вызовов количество рекурсивных вызовов растет пропорционально уменьшению размера работы, то есть сложность решения подзадач на каждом уровне остается одинаковой, поэтому общая работа равна$f(n)$ помноженному на количество уровней дерева -
$a < b^c$ ,$T(n)=O(f(n) * \log n)$ . С каждым уровнем дерева вызовов количество рекурсивных вызовов растет медленнее, чем уменьшается размер работы, то есть сложность решения подзадач на каждом уровне уменьшается, поэтому асимптотически общая работа определяется работой на верхнем уровне дерева
Бинарный поиск можно выразить следующей рекуррентной формулой:
Здесь:
-
$a=1$ , так как алгоритм порождает только одну подзадачу: поиск элемента в левой или правой части массива -
$b=2$ , так как размер подзадач каждый раз сокращается вдвое, так как мы разделяем массив на две части -
$f(n) = O(1)$ , так как вся работа, которую мы делаем на подзадаче - вычисление mid индекса + сравнение, что занимает константное время -
$c=0$ , так как$O(1) = O(n^0)$
Здесь сложность решения подзадач одинакова на каждом уровне дерева вызовов, так как на каждом уровне мы имеем всегда 1
подзадачу с одинаковой работой. Действительно,
Обход двоичного дерева можно выразить так:
Здесь:
-
$a=2$ , так как алгоритм порождает две подзадачи: обход левого и правого поддеревьев -
$b=2$ , так как размер подзадач каждый раз сокращается вдвое, ведь вызывая обход на левом или правом поддереве, мы сокращаем количество нод, которое нужно обойти, в 2 раза. То есть, для дерева с$n$ элементов$n/2$ элементов находятся в левом поддерева, а остальные$n/2$ - в правом -
$f(n) = O(1)$ , так как вся работа, которую мы делаем на подзадаче - это чтение ключа текущей ноды -
$c=0$ , так как$O(1) = O(n^0)$
Здесь сложность решения подзадач возрастает с каждым уровнем дерева, так как количество вызовов возрастает, а работа
остается константной. Действительно,
Merge Sort можно выразить так:
Здесь:
-
$a=2$ , так как алгоритм порождает две подзадачи: merge sort левой и правой части массива -
$b=2$ , так как мы разделяем массив на 2 равные части -
$f(n) = O(n)$ , так как нам нужно разделить массив на 2 части$O(1)$ + слить отсортированные подмассивы в один: скопировать подмассивы, пройтись по ним, и положить элементы в результирующий массива, что займет$O(n)$ , поэтому работа на каждом уровне равна$O(n)$ -
$c=1$ , так как$O(n)=O(n^1)$
Здесь на каждом уровне дерева вызовов мы имеем одинаковую работу, так как количество вызовов растет пропорционально
уменьшению работы. Действительно,