算法的递归关系

本文概述

• 1.替代方法
• 2.迭代方法

递归是一个方程或不等式, 用较小输入上的值描述一个函数。解决递归关系意味着获得在满足递归的自然数上定义的函数。

例如, 递归描述了MERGE SORT程序的最坏情况运行时间T（n）。

T (n) = θ (1) if n=1
 2T + θ (n) if n>1

有四种解决递归的方法：

1. 替代方法
2. 迭代方法
3. 递归树方法
4. 主法

---

1.替代方法

替换方法包括两个主要步骤：

1. 猜猜解决方案。
2. 使用数学归纳法找到边界条件, 并证明猜测是正确的。

例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) = 1  if 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 times

T (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).

---