recursion - 如何根据递归关系确定递归树的高度？

Question

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

alt text http://homepages.ius.edu/rwisman/C455/html/notes/Chapter4/ch4-9.gif

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

Answer 1

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

例如，2T(n/2) + n 递归将具有深度 lg(n) 的树(n 的以 2 为底的对数)。