Lesson 06

递归

常量降级快速 review

Hanoi 塔

要把 n 个板子从 A 挪到 C 柱子，你可以有 B 柱子使

两个函数

$S(n, a, b, c)$

有 3 个柱子 a b c，将 n 个板子从 a 挪到 c

$move(a, b)$

将 1 个板子从 a 挪到 b

倍数降级

套路

假设你已经拿到了 n/2 的问题的答案

想一下是否可以通过这个答案解决 n 的问题的答案

思路案例

问题

求 n 个数的最大值

对照表

标题	对照
大小为 n 的问题	如何求出 n 个数的最大值
大小为 n 的答案 $S(n)$	n 个数的最大值
大小为 n/2 的问题	如何求出前一半数的最大值
大小为 n/2 的答案 $S(n/2)$	前一半数的最大值

思路

假设我已经知道了前 n/2 个数的最大值，

想一下是否可以通过这个值求出 n 个数的最大值呢

训练

求 2 的 n 次方

递归下的时间复杂度分析

代数法

算法

 $Power2(n)$

     $\text{if } n = 1 \text{ then}$

         $\text{return } 2$

     $\text{return } Power2(n - 1) * 2;$

分段分析

 $T(n) = O(1) \text{ when } n = 1$

        $T(n - 1) + c \text{ when } n > 1$

求值

 $T(n) = c + T(n - 1)$

      $= c + (c + T(n - 2))$

      $= c + (c + (c + T(n - 3)))$

      $= ...$

      $= c + c + c + ... + c + O(1)$

      $= c + c + c + ... + c + c_2$

      $= cn + c_2$

      $= O(n)$

递归树法

公式

 $T(n) = O(1) \text{ when } n = 1$

        $2 \cdot T(n/2) + c \text{ when } n > 1$

分叉

计算

计算每层的总合

 $T(n) = c + 2c + 4c + ... + xc + n \cdot c_2$

      $= 2^0c + 2^1c + 2^2c + ... + 2^kc + n \cdot c_2$

      $= 2 \cdot 2^kc - 1 + n \cdot c_2$

        $k = log_2{n}$

      $= 2 \cdot n \cdot c - 1 + n \cdot c_2$

      $= O(n)$

尝试

1

1 2 3 4 5 6 7 8 9 10 
public int power2(int n) {    if (n == 1) {        return 2;    }    int result = power2(n / 2) * power2(n / 2);    if (n % 2 == 1) {        result *= 2;    }    return result;}

2

1 2 3 4 5 6 7 8 9 10 11 
public int power2(int n) {    if (n == 1) {        return 2;    }    int half = power2(n / 2);    int result = half * half;    if (n % 2 == 1) {        result *= 2;    }    return result;}

分区Partition

分区思维

思路

不直接解决问题

转而去想，我能不能把问题拆成 2 个，分别解决，

或者，在有可能的情况下，扔掉 1 个

二叉搜索Binary Search

问题

给定一个升序序列 $A = <A_1, A_2, ... , A_n>$

找到这个序列里是否存在一个数 $q$

任务

代码

时间复杂度分析

递归 Basecase 分析

找相对低的值，尝试，看最后问题都落到了多少规模的。

sublist 复杂度解除

传参

作业

字符反转

Q34

数列生成

Q33

表达式求值

Q32