递归算法时间复杂度的计算方程式一个递归方程:
在引入递归树之前可以考虑一个例子:
还可以继续迭代将其完全展开可得:
将(1)式小括号展开,可得:
这恰好是一个树形结构由此可引出递归树法。
图中的(a)(b)(c)(d)分别是递归树生成的第1,2,3,n步每一节点中都将当前的自由项n2留在其中,而将两個递归项T(n/2) + T(n/2)分别摊给了他的两个子节点如此循环。
图中所有节点之和为:
可知其时间复杂度为O(n2)
可以得到递归树的规则为:
(2) 烸个节点的分支数为k;
(3)每层的右侧标出当前层中所有节点的和
其递归树如下图所示:
可见每层的值都为n,从根到叶节点的朂长路径是: