如何根据递归关系确定递归树的高度？ [英] How to determine the height of a recursion tree from a recurrence relation?

问题描述

如何确定在处理递归运行时时构建的递归树的高度？它与确定规则树的高度有何不同？

How does one go about determining the height of a recursion tree, built when dealing with recurrence run-times? How does it differ from determining the height of a regular tree?

替代文字http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

编辑：抱歉，我的意思是添加如何从递归关系中获取递归树的高度 。

edit: sorry, i meant to add how to get the height of the recursion tree from the recurrence relation.

推荐答案

如果递归的形式为T（n）= aT（n / b）+ f（n），则树的深度为n的对数底b。

If recurrence is in the form of T(n) = aT(n/b) + f(n) then the depth of the tree is log base b of n.

例如，2T（n / 2）+ n次重复将具有深度为lg（n）的树（n的对数为2）。

For example, 2T(n/2) + n recurrence would have tree of depth lg(n) (log base 2 of n).

这篇关于如何根据递归关系确定递归树的高度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！