递归式求解

た入场券 2021-10-18 07:50 1060阅读 0赞

## 1. 主定理 ##

### 1.1 主定理介绍 ###

![1522393-20190619093933717-911651906.png][]

### 1.2 不能使用主定理的情况 ###

（1）T(n)不是单调函数，(e.g. T(n) = sinx)

（2）f(n)不是多项式函数 (e.g. T(n) = T(n/2) + 2n)

（3）b不能表示为一个常量（e.g. T(n) = 2T(√n））

### 1.3 举例说明 ###

**(1) T(n) = T(n/2) + 1/2 \* n2 \+ n**

解：

此时 a = 1, b = 2, f(n) =  1/2\*n2 + n

故 nlogba = n0= 1

f(n) = Ω(nlogba+2)，ε=2，且当 C = 1/4时，满足第三种情况的条件

故第三种情况成立，T(n) = θ(n2)

**(2) T(n) = 2T(n/4) + √n + 42**

解：

此时 a = 2, b = 4, f(n) = √n + 42

故 nlogba = n1/2

所以 f(n) = Θ(nlogba)

故第二种情况成立，T(n) = Θ(nlogba\*logn) = Θ(√n\*logn)

**(3) T(n) = 3T(n/2) + 3/4\*n + 1**

解：

此时 a = 3, b = 2, f(n) = 3/4\*n + 1

故 nlogba = n

所以 f(n) = O(nlogba-(logba-1))，ε = logba-1 = log23-1 > 0，

故第一种情况成立，T(n) = Θ(nlogba) =  Θ(nlog23)

## 2. 递归树 ##

递归树是一棵结点带权值的树。初始的递归树只有一个结点，它的权标记为T(n)；然后按照递归树的迭代规则不断进行迭代，每迭代一次递归树就增加一层，直到树中不再含有权值为函数的结点（即叶结点都为T(1)T(1)）。下面以递归方程

![1522393-20190619102141728-1021236444.png][]

为例讲解递归树。

首先这道题肯定是没法用主定理，所以画递归树：

![1522393-20190626192009487-490123551.jpg][]

因为每次两个分支大小不相同，故这颗树实际上并不像画出来这样的平衡，故树高度最高为log2n，最低为log4n

我们假设极限树高为log2n，即最大高度，且为平衡树，此时可以得到时间复杂度的上界:

![1522393-20190626192542231-1781208531.png][]

同理当极限树高为log4n时，得到时间复杂度的下界：

![1522393-20190626192907984-738077018.png][]

故可知时间复杂度为

![1522393-20190626193028020-257769240.png][]

## 3. 找规律 ##

**T(n) = 2T(n-1) + 1（T(1) = 1)**

这道题是不是看起来很像高中学的等比数列递推式，是的！

如果方程右端出现T(n-1)这种式子，很有可能是递推式，再观察是等比还是等差数列，这道题很像等比，所以构造

AT(n)+B = 2(T(n-1)+B)

再和原式比较，得A = 1, B = 1，也就是说 T(n) +1 = 2(T(n-1) + 1)

首项为T(1)+1 = 2，所以得通项公式为：

**T(n) + 1 = 2\*2n-1 = 2n**

不过对于这类题还有一种更通用的公式很方便：

![1522393-20190619154632602-1174711283.png][]

对于这道题来说，c=1，b=2，g(n)=1，代入方程得：

![1522393-20190619154915135-113099650.png][]

与前面做法得到得结果相同

转载于:https://www.cnblogs.com/RB26DETT/p/11050055.html

[1522393-20190619093933717-911651906.png]: /images/20211018/2e027cc12a304035a5c120fafab3c7ab.png
[1522393-20190619102141728-1021236444.png]: /images/20211018/c043f84cb6b345c7997db119ce1e433a.png
[1522393-20190626192009487-490123551.jpg]: /images/20211018/af8e77d669c744b6b403ba45e2373f53.png
[1522393-20190626192542231-1781208531.png]: /images/20211018/8d7765dccc3644fe93e2146bc5612797.png
[1522393-20190626192907984-738077018.png]: /images/20211018/5ece27f4ed884a378f76ad48575ac6d9.png
[1522393-20190626193028020-257769240.png]: /images/20211018/6bad3f50bd11487f8fdaa01ca8cb57b9.png
[1522393-20190619154632602-1174711283.png]: /images/20211018/37724ee2b73c481c8b562d484f1419b0.png
[1522393-20190619154915135-113099650.png]: /images/20211018/75360cfbe13f46e1bfdcb217d10deb50.png