本文概述
- 1.替代方法
- 2.迭代方法
例如, 递归描述了MERGE SORT程序的最坏情况运行时间T（n）。
T (n) = θ (1) if n=1
2T + θ (n) if n>
1有四种解决递归的方法：
- 替代方法
- 迭代方法
- 递归树方法
- 主法
- 猜猜解决方案。
- 使用数学归纳法找到边界条件, 并证明猜测是正确的。
T (n) = T + n我们必须证明它被O渐近约束（log n）。
解：
For T (n) = O (log n)我们必须证明对于某些常数c
T (n) ≤c logn.将其放在给定的递归方程中。
T (n) ≤c log+ 1
≤c log+ 1 = c logn-clog2 2+1
≤c logn for c≥1
Thus T (n) =O logn.例2考虑递归
T (n) = 2T+ n n>
1在T上找到一个渐近边界。
解：
We guess the solution is O (n (logn)).Thus for constant 'c'.
T (n) ≤c n logn
Put this in given Recurrence Equation.
Now, T (n) ≤2clog +n
≤cnlogn-cnlog2+n
=cn logn-n (clog2-1)
≤cn logn for (c≥1)
Thus T (n) = O (n logn).2.迭代方法这意味着扩展递归并将其表示为n项和初始条件的总和。
例1：考虑重复发生
T (n) = 1if n=1
= 2T (n-1) if n>
1解：
T (n) = 2T (n-1)
= 2[2T (n-2)] = 22T (n-2)
= 4[2T (n-3)] = 23T (n-3)
= 8[2T (n-4)] = 24T (n-4)(Eq.1)Repeat the procedure for i timesT (n) = 2i T (n-i)
Put n-i=1 or i= n-1 in(Eq.1)
T (n) = 2n-1 T (1)
= 2n-1 .1{T (1) =1 .....given}
= 2n-1例2：考虑重复发生
T (n) = T (n-1) +1 and T (1) =θ (1).【算法的递归关系】解：
T (n) = T (n-1) +1
= (T (n-2) +1) +1 = (T (n-3) +1) +1+1
= T (n-4) +4 = T (n-5) +1+4
= T (n-5) +5= T (n-k) + k
Where k = n-1
T (n-k) = T (1) = θ (1)
T (n) = θ (1) + (n-1) = 1+n-1=n= θ (n).
