Как определить высоту дерева рекурсии из рекуррентного отношения?

Если рекуррентность представлена ​​в виде T(n) = aT(n/b) + f(n), то глубина дерева равна логарифмической базе b числа n.

Например, повторение 2T (n/2) + n будет иметь дерево глубины lg (n) (логарифмическое основание 2 от n).

Во-первых, если это вопрос домашнего задания, отметьте его как таковой. Изображения, на которые вы ссылаетесь, подразумевают, что вы находитесь в CS 455 с профессором Висманом. :)

Главный совет, который я дам, таков: высота дерева, очевидно, определяется тем, когда вы добираетесь до «листьев». Листья дерева, моделирующие рекуррентное отношение функции, являются базовым случаем. Таким образом, я бы посмотрел, как «быстро» N может сжаться до базового случая.

Глубина любого дерева — это наименьшее количество ребер от узла до корневого узла дерева. Глубина корневого узла равна 0.

Рассмотрим рекурсию T(n)=aT(n/b). Это приводит к следующему дереву рекурсии

Ясно, что глубина дерева равна $\log_b n$ Глубина равна высоте дерева.

Высота дерева рекурсии зависит от рассматриваемого рекурсивного алгоритма. Не все алгоритмы «разделяй и властвуй» имеют деревья одинаковой высоты, как и не все древовидные структуры имеют одинаковую высоту. Если вы не можете определить максимально возможную высоту алгоритма или вам нужно вычислить фактическую высоту дерева во время выполнения, вы можете использовать глобальную переменную для рекурсивной функции, увеличивать ее при входе в функцию и уменьшать это при выходе из функции. Эта переменная будет указывать текущий уровень рекурсивной процедуры. При необходимости вы можете сохранить максимальное значение этой переменной во второй переменной.

Что, для вас неочевидно? ;) Это отличный вопрос хотя бы по той причине, что людям нравится махать на него руками. Впрочем, с практикой все становится ясно.

Вот объяснение, основанное на примере из Введения в алгоритмы Кормена и др., Раздел 4.4.

Рассмотрим T(n) = 3T(n/4) + cn^2. Отношение сообщает временную сложность задачи (например, массива) размером n. Важно помнить, что представляет собой n. Поскольку сложность T определяется в терминах T, это рекуррентное соотношение.

Если высота не очевидна, мы можем последовать совету Polya и попытаться использовать прямой рассуждения, нарисовать картину или решить какую-то связанную проблему. Мы можем использовать прямые рассуждения, просто подставляя правое выражение для T везде, где появляется T,

T(n) = 3T(n/4) + cn^2
     = 3[3T( (n/4)/4 ) + c(n/4)^2] + cn^2
     = 9T(n/16) + c(n/4)^2 + cn^2
     = 9[3T( (n/16)/4 ) + c(n/16)^2] + c(n/4)^2 + cn^2
     = 27T(n/64) + c(n/16)^2 + c(n/4)^2 + cn^2
     ...

Нарисовав изображение, мы получим дерево. Каждая рекурсия создает три ветви для каждого потомка:

Initial pass
                   ____cn^2____
                  /      |     \
                 /       |      \
            T(n/4)    T(n/4)    T(n/4)


First recursion                 
                   ____cn^2____
                  /      |     \
                 /       |      \
          cn(n/4)^2  cn(n/4)^2  cn(n/4)^2
          /   |   \  /   |   \  /   |   \
       T(n/16)          ...            T(n/16)
                         .
...on down             
                   ____cn^2____
                  /      |     \
                 /       |      \
          cn(n/4)^2  cn(n/4)^2  cn(n/4)^2
          /   |   \  /   |   \  /   |   \
       T(n/16)          ...            T(n/16)
                         .
                         .
                         .
    T(1) ...                            ...  T(1)

На что?

Помните, что n – это размер исходной задачи (например, количество элементов в массиве)¹. Это ограничивает количество возможных рекурсий. Граничные условия будут зависеть от ситуации, в которой произошла рекурсия. Для массива вы можете представить себе рекурсию, продолжающуюся до тех пор, пока не останется только один элемент. Это произойдет в Т(1).

Как граница может быть связана с высотой?

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

На каком уровне дерево достигает граничного условия?

Глядя на отношение или дерево, обратите внимание, как n/4 неоднократно подключается к последовательным рекурсиям. Это означает, что размер подзадачи (где n — исходный размер задачи) равен n/4^i на i уровне. На границе размер подзадачи равен 1:

                n/4^i = 1
         log_4(n/4^i) = log_4(1)
log_4(n) - log_4(4^i) = 0
             log_4(n) = log_4(4^i)
             log_4(n) = i

Последнее уравнение говорит нам, что дерево достигает граничного условия, когда i = log_4(n). Поскольку высота дерева — это уровень, на котором выполняется граничное условие, дерево имеет высоту log_4(n).

Отсюда нужно только обобщить, чтобы прийти к выводу, который @ejel дает, что

Если T(n) = aT(n/b) + f(n), то глубина дерева равна логарифмической базе b числа n.

Как указывает @xpda, высота дерева рекурсии будет зависеть от алгоритма. Один вывод, который, вероятно, обобщает, заключается в рассмотрении того, как алгоритм ведет себя на своих границах.

¹ Слово «проблема» может использоваться по-разному. В первую очередь это может означать стоящую перед вами задачу, например, найти высоту дерева рекурсии. Однако, поскольку дерево возникает в результате рекурсии, проблема снова появляется в аналогичной форме (т. Е. Поддеревьях), так что проблема означает размер обрабатываемого множества, например количество элементов в массиве.