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

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

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

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

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

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