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

Question

Как можно определить высоту дерева рекурсии, построенного при работе с рекурсивным временем выполнения? Чем он отличается от определения высоты обычного дерева?

альтернативный текст http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

edit: извините, я хотел добавить, как получить высоту дерева рекурсии из отношения рекурсии .

Answer 1

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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