Алгоритмы (теория/практика): Часть 6.2. «Разделяй и властвуй» (продолжение)

Метод деревьев рекурсии

Метод деревьев рекурсии предполагает более изящный способ нахождения предполагаемого решения для дальнейшей его проверки методом подстановки. Конечно, сам метод можно использовать для доказательства правильности решения, но для этого нужно тщательно его проанализировать и просуммировать время на каждом уровне.

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

Мы попробуем найти его верхнюю границу (\(O(g\left( n \right) )\)). Давайте сначала устно проанализируем его, а потом построим дерево. В принципе, зачастую простого анализа бывает достаточно, но для наглядности рекомендуется строить деревья.

Запись \(2T(\left\lfloor { n }/{ 2 } \right\rfloor )\) говорит о том, что при каждом рекурсивном вызове массив данных сокращается вдвое, затем происходит два рекурсивных вызова этой же самой функции. Также в каждом вызове выполняется некоторая функция, которая описывается при помощи обозначения \(\Theta (n)\). Именно эта операция и будет определять итоговую стоимость каждого узла. Для удобства мы обозначим её как \(cn\), где \(c\) – константа.

В самом верху дерева будет располагаться узел \(cn\), обозначающий время самого верхнего уровня рекурсии. Каждый узел дерева является корнем еще для двух поддеревьев, которые описывают выполнение алгоритма для \({ n }/{ 2 }\). Каждый уровень будет комбинацией вызовов для определенной доли \(n\).

Хорошо, мы также можем подсчитать количество уровней. Давайте сделаем это вместе. Каждый раз массив данных делится на две части и происходит два рекурсивных вызова. Это продолжается до тех пор, пока в массиве не останется только один элемент. Мы уже говорили о том, что количество делений массива на два равняется \(\log _{ 2 }{ n }\). А значит, всего количество уровней (вместе с корневым) будет \(\log _{ 2 }{ n }+1\), при этом глубина уровня считается от 0 (самый верхний) и до \(\log _{ 2 }{ n }\) (самый нижний).

Количество узлов на каждом уровне мы также можем подсчитать. На нулевом уровне 1 узел. На первом – 2 узла, на втором – 4 и т.д. Значит количество узлов будет равняться \({ 2 }^{ i }\), где \(i\) – глубина уровня. Размер массива в каждом узле будет равняться \({ n }/{ { 2 }^{ i } }\).

Рано или поздно рекурсия достигнет самого нижнего уровня, на котором будет \({ 2 }^{ { i }_{ max } }={ 2 }^{ \log _{ 2 }{ n } }={ n }^{ \log _{ 2 }{ 2 } }=n\) узлов. Вклад каждого узла в общее время работы является константным выражением, которое мы обозначим как \(T(1)\). Выходит, что общее время работы нижнего уровня будет представлять собой \(nT(1)\) или \(\Theta (n)\).

Изобразим наше дерево (я сделал изображением, ибо понятия не имею как в WP можно делать такие штуки; кликните, чтобы открыть в новой вкладке):

Суммарное время каждого уровня — \({ 2 }^{ i }({ cn }/{ { 2 }^{ i } })\). Значит, чтобы найти время всех уровней, нужно их просуммировать:

Наш пример довольно прост, поэтому далеко необязательно записывать так, но я делаю всё в общем виде.

Хорошо, мы получили общее значение времени функции. Теперь нам не составит труда воспользоваться асимптотическим обозначением верхней границы:

Таким образом мы сделали предположение о том, что сложность нашего алгоритма равняется \(O(n\log _{ 2 }{ n } )\). Давайте это проверим с помощью метода подстановки. Константа \(с\) уже задействована, поэтому покажем корректность неравенства для некоторой константы \(d>0\):

Подставим и избавимся от округления:

Сократим и воспользуемся свойством логарифмов:

\(\log _{ 2 }{ 2 } =1\), поэтому

Неравенство верно при \(d\ge c\). Наша догадка оказалась верной.

Основной метод

Для решения этим способом необходимо научиться применять основную теорему. Я приведу её практически в точном виде, а потом мы подробнее её рассмотрим на конкретном примере.

Основной метод применяется для решения соотношений вида

где \(a\ge 1\) и \(b>1\) — константы, а \(f\left( n \right)\) – асимптотически положительная функция, \({ n }/{ b }\) интерпретируется либо как \(\left\lfloor { n }/{ b } \right\rfloor\), либо как \(\left\lceil { n }/{ b } \right\rceil \). В этом случае \(T(n)\) имеет следующие асимптотические границы:

1. Если \(f\left( n \right)=O({ n }^{ \log _{ b }{ a } -\epsilon })\) для некоторой константы \(\epsilon >0\), то \(T(n)=\Theta ({ n }^{ \log _{ b }{ a } })\).
2. Если \(f\left( n \right)=\Theta ({ n }^{ \log _{ b }{ a } })\), то \(T(n)=\Theta ({ n }^{ \log _{ b }{ a } }\log _{ 2 }{ n } )\).
3. Если \(f\left( n \right) =\Omega ({ n }^{ \log _{ b }{ a } +\epsilon })\) для некоторой константы \(\epsilon >0\) и если \(af\left( { n }/{ b } \right) \le cf\left( n \right) \) для некоторой константы \(c \lt 1\) и всех достаточно больших \(n\), то \(T(n)=\Theta(f\left( n \right))\).

Для использования основного метода, нужно просто взять конкретное рекуррентное соотношение, посмотреть какой из случаев применим к нему и сделать вывод о его решении. Конечно же, некоторые соотношения не попадут ни в один из трёх случаев. Для них основной метод не работает.

Хорошо, давайте теперь рассмотрим несколько примеров. Здесь мы опустим округление \({ n }/{ b }\), так как на решение это всё равно никаким образом не повлияет. А если нет разницы, зачем платить больше?

Уже знакомое нам соотношение. Здесь \(a=2, b=2, f\left( n \right)=n\). В этом случае конструкция \({ n }^{ \log _{ b }{ a } }\) преобразуется в \({ n }^{ \log _{ 2 }{ 2 } }={ n }^{ 1 }=n\). А это значит, что \(f\left( n \right) =\Theta (n)\). Это второй случай, поэтому наше решение будет таким: \(T(n)=\Theta ({ n }^{ \log _{ b }{ a } }\log _{ 2 }{ n } )=\Theta ({ n }^{ \log _{ 2 }{ 2 } }\log _{ 2 }{ n } )=\Theta (n\log _{ 2 }{ n } )\).

\(a=16,b=4,f\left( n \right) =n,{ n }^{ \log _{ b }{ a } }={ n }^{ \log _{ 4 }{ 16 } }={ n }^{ 2 }\). В этом случае \(f\left( n \right) =O({ n }^{ 2-\epsilon })\), так как можно найти константы \(c\) и \(\epsilon \), которые бы сделали это неравенство верным: \(n\le { c{ n }^{ 2 } }/{ { n }^{ \epsilon } }\). А это значит, что в этом случае решение будет таким: \(T(n)=\Theta ({ n }^{ 2 })\).

Внимательность: конструкция \(O({ n }^{ \log _{ b }{ a } -\epsilon })\) из первого случая преобразуется в \(O({ { n }^{ \log _{ b }{ a } } }/{ { n }^{ \epsilon } })\). То есть функция \(f\left( n \right)\) должна быть не просто меньше \(g\left( n \right)\) (той, что стоит в скобочках), а меньше на определенный множитель \({ n }^{ \epsilon }\). Я очень хочу, чтобы вы не упустили этот момент.

\(a=4,b=2,f\left( n \right) ={ n }^{ 3 },{ n }^{ \log _{ b }{ a } }={ n }^{ \log _{ 2 }{ 4 } }={ n }^{ 2 }\). \(f\left( n \right) =\Omega ({ n }^{ 2+\epsilon })\), так как есть константы \(с\) и \(\epsilon \) такие, что \(c{ n }^{ 2 }{ n }^{ \epsilon }\le { n }^{ 3 }\). Теперь нужно проверить условие \(af\left( { n }/{ b } \right) \le cf\left( n \right) \). Подставим и получим \({ { n }^{ 3 } }/{ 2\le c{ n }^{ 3 } }\). Условие выполняется, например, при \(c=\frac { 1 }{ 2 }.\) А это значит, что в этом случае решение выглядит так: \(T(n)=\Theta ({ n }^{ 3 })\).

Обоснование того, почему этот метод вообще работает я приводить не буду. Когда-то давно умные дяди это всё доказали и обосновали. Применять метод можно и без знания того, что находится «под капотом». Но если вдруг интересно, то полное доказательство вы сможете найти в книге «Алгоритмы. Построение и анализ» на странице 123.

А у меня всё. Получилось как-то сухо и сжато в этот раз. Я вроде обещал писать интересным языком, но опять скатился в простое изложение фактов. Постараюсь исправиться в дальнейшем.

Спасибо, что читаете. До скорых встреч.

Предыдущая статья