<算法导论>学习笔记(3)--递归树求递归算法时间复杂度

向右看齐 2022-08-24 14:10 233阅读 0赞

**<算法导论>学习笔记(3)--递归树求递归算法时间复杂度**

Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.

是否具有扎实的算法知识和技术基础，是区分真正熟练的程序员与新手的一项重要特征。

递归算法时间复杂度的计算方程式一个递归方程：

![2010122110093855.jpg][]

在引入递归树之前可以考虑一个例子：

T(n) = 2T(n/2) + n2

迭代2次可以得：

T(n) = n2 \+ 2(2T(n/4) + (n/2) 2)

还可以继续迭代，将其完全展开可得：

T(n) = n2 \+ 2((n/2) 2 \+ 2((n/22)2 \+ 2((n/23) 2 \+ 2((n/24) 2 \+…+2((n/2i) 2 \+ 2T(n/2i + 1)))…))))　　……(1)

而当n/2i+1 == 1时，迭代结束。

将(1)式小括号展开，可得：

T(n) = n2 \+ 2(n/2)2 \+ 22(n/22) 2 \+ … + 2i(n/2i)2 \+ 2i+1T(n/2i+1)

这恰好是一个树形结构，由此可引出递归树法。

![2010122110500693.gif][]

图中的(a)(b)(c)(d)分别是递归树生成的第1,2,3,n步。每一节点中都将当前的自由项n2留在其中，而将两个递归项T(n/2) + T(n/2)分别摊给了他的两个子节点，如此循环。

图中所有节点之和为:

\[1 + 1/2 + (1/2)2 \+ (1/2)3 \+ … + (1/2)i\] n2 = 2n2

可知其时间复杂度为O(n2)

可以得到递归树的规则为：

(1) 每层的节点为T(n) = kT(n / m) + f(n)中的f(n)在当前的n/m下的值；

(2) 每个节点的分支数为k；

(3)每层的右侧标出当前层中所有节点的和。

再举个例子：

T(n) = T(n/3) + T(2n/3) + n

其递归树如下图所示：

![2010122111092387.gif][]

可见每层的值都为n，从根到叶节点的最长路径是：

![2010122111104433.gif][]

因为最后递归的停止是在(2/3)kn == 1.则

![2010122111430244.gif][]

于是

![2010122111434841.gif][]

即T(n) = O(nlogn)

总结，利用此方法解递归算法复杂度：

f(n) = af(n/b) + d(n)

1.当d(n)为常数时：

![2010122111483652.jpg][]

2.当d(n) = cn 时：

![2010122111491222.jpg][]

3.当d(n)为其他情况时可用递归树进行分析。

由第二种情况知，若采用分治法对原算法进行改进，则着重点是采用新的计算方法缩小a值。

**学习的路上,与君共勉。**

[2010122110093855.jpg]: /images/20220824/deb790de1d674b05b785be97254fb208.png
[2010122110500693.gif]: /images/20220824/bdcba052f2734db5a170e7f139bf0644.png
[2010122111092387.gif]: /images/20220824/e5a7d914dfd1467f9c18454a3357494e.png
[2010122111104433.gif]: /images/20220824/a4ed3423d0b84b71a6ad0577f0dc0db0.png
[2010122111430244.gif]: /images/20220824/a7633cf433224d778c03bdfee30cab1f.png
[2010122111434841.gif]: /images/20220824/619b0e510e184a84b3885ec3d02c95dc.png
[2010122111483652.jpg]: /images/20220824/8e6be15666c84e69bdec4e2f73c94b4b.png
[2010122111491222.jpg]: /images/20220824/5b3c696509a94540bb847fa57283348e.png