递归

思路

1. 确定问题是否能够使用递归进行求解.
2. 推导出递推关系,即父问题与子问题的关系, 以及递归的结束条件

例如之前遍历链表的递推关系为:
$f(n)=\begin{cases} stop, n=null\\ f(n.next), u\neq null\end{cases}$

• 深入到里层的叫做递
• 从最里层出来的叫做归
• 在递的过程中,外层函数内的局部变量(以及方法参数),并不不会消失,归的时候还可以继续使用.

时间复杂度计算

主定理

1. 如果有递归式:

2. 其中:

• T(n) : 是问题的运行时间, n是问题的规模
• a : 子问题的个数(一个递归内部被分为几个小递归)
• T(${\frac{n}{b}}$) 是子问题运行时间,每个子问题被拆分成原问题数据规模的${\frac{n}{b}}$, 比如b为2,就说明原问题的数据规模被拆解成了一半
• f(n) 是除了递归外执行的计算.

3. 令 x = $\log_b{a}$,即 (x=log子问题缩小倍数) 的子问题个数

那么就有:

主定理求解时间复杂度例子

1. $T(n) = 2T({\frac{n}{2}}) + n^4$

   • 本例中: $x = \log_2{2} = 1$ , $f(n) = O(n^c) = n^4$,则c=4
   • 因为 c > x 所以时间复杂度为: $\Theta(n^4)$

2. $T(n)=T(\frac{7n}{10}) + n$

   • x = 0 , c = 1, c > x, 所以时间复杂度为: $\Theta(n)$

3. $T(n) = 16T(\frac{n}{4})+n^2$

   • 此时 x = 2, c = 2. 所以时间复杂度为 $\Theta(n^2log_n)$

递推方式求解时间复杂度

有一些递归式符合上面主定理求解的方式, 有些不符合, 一般来说都是每次递归后规模的缩小不是成比例的, 比如下面的例子.

例子:

1. 递归求和

   public long sum(long n){
        if(n == 1){
            return 1;
        }
        return n + sum(n-1);
   }
   

递归式: $T(n) = T(n-1) +c, T(1) = c$

下面为展开过程:

$T(n) = T(n - 2) + c + c$
$T(n) = T(n - 3) + c + c + c$
...
$T(n) = T(1) + (n-1)c = nc$
时间复杂度为O(n)

一个推导公式的网站: wolframalpha (opens new window)

• 例1: 输入f(n) = f(n-1) + c,f(1) =c
• ...