【算法之旅】基础算法之递归

以你之姓@ 2023-09-25 20:20 138阅读 0赞

![请添加图片描述][ea689b325bd64e3d99e44e943c5dbdb3.png]  
一名软件工程专业学生的算法之旅，记录自己从零开始学习数据结构与算法，从小白的视角学习数据结构：数组、对象/结构、字符串、队列、栈、树、图、堆、平衡树/线段树等，学习算法：枚举、排序、搜索、计数、分治策略、动态规划、贪心、回溯、图论、数论、字符串算法等，欢迎加入我，一起来学吧！

#### 基础算法之递归 ####

*   *   *  一、概述
         *  二、单路递归 Single Recursion
         *  三、多路递归 Multi Recursion
         *  四、递归优化-记忆法
         *  五、递归优化-尾递归
         *  六、递归时间复杂度-Master theorem\[^14\]
         *  七、递归时间复杂度-展开求解
     *

#### 一、概述 ####

**定义**

计算机科学中，递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小子集

> In computer science, **recursion** is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

比如单链表递归遍历的例子：

void f(Node node) {
        
        if(node == null) {
        
            return;
        }
        println("before:" + node.value)
        f(node.next);
        println("after:" + node.value)
    }

说明：

1.  自己调用自己，如果说每个函数对应着一种解决方案，自己调用自己意味着解决方案是一样的（有规律的）
2.  每次调用，函数处理的数据会较上次缩减（子集），而且最后会缩减至无需继续递归
3.  内层函数调用（子集处理）完成，外层函数才能算调用完成

**原理**

假设链表中有 3 个节点，value 分别为 1，2，3，以上代码的执行流程就类似于下面的**伪码**

// 1 -> 2 -> 3 -> null  f(1)
    
    void f(Node node = 1) {
        
        println("before:" + node.value) // 1
        void f(Node node = 2) {
        
            println("before:" + node.value) // 2
            void f(Node node = 3) {
        
                println("before:" + node.value) // 3
                void f(Node node = null) {
        
                    if(node == null) {
        
                        return;
                    }
                }
                println("after:" + node.value) // 3
            }
            println("after:" + node.value) // 2
        }
        println("after:" + node.value) // 1
    }

**思路**

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

例如之前遍历链表的递推关系为  
 f ( n ) = \{ 停止 n = n u l l f ( n . n e x t ) n ≠ n u l l f(n) = \\begin\{cases\} 停止& n = null \\\\ f(n.next) & n \\neq null \\end\{cases\} f(n)=\{ 停止f(n.next)n=nulln=null

*  深入到最里层叫做**递**
 *  从最里层出来叫做**归**
 *  在**递**的过程中，外层函数内的局部变量（以及方法参数）并未消失，**归**的时候还可以用到

#### 二、单路递归 Single Recursion ####

**E01. 阶乘**

用递归方法求阶乘

*  阶乘的定义  n ! = 1 ⋅ 2 ⋅ 3 ⋯ ( n − 2 ) ⋅ ( n − 1 ) ⋅ n n!= 1⋅2⋅3⋯(n-2)⋅(n-1)⋅n n!=1⋅2⋅3⋯(n−2)⋅(n−1)⋅n，其中  n n n 为自然数，当然  0 ! = 1 0! = 1 0!=1
 *  递推关系

f ( n ) = \{ 1 n = 1 n ∗ f ( n − 1 ) n > 1 f(n) = \\begin\{cases\} 1 & n = 1\\\\ n \* f(n-1) & n > 1 \\end\{cases\} f(n)=\{ 1n∗f(n−1)n=1n>1

代码

private static int f(int n) {
        
        if (n == 1) {
        
            return 1;
        }
        return n * f(n - 1);
    }

拆解**伪码**如下，假设 n 初始值为 3

f(int n = 3) {
         // 解决不了,递
        return 3 * f(int n = 2) {
         // 解决不了,继续递
            return 2 * f(int n = 1) {
        
                if (n == 1) {
         // 可以解决, 开始归
                    return 1;
                }
            }
        }
    }

**E02. 反向打印字符串**

用递归反向打印字符串，n 为字符在整个字符串 str 中的索引位置

*  **递**：n 从 0 开始，每次 n + 1，一直递到 n == str.length() - 1
 *  **归**：从 n == str.length() 开始归，从归打印，自然是逆序的

递推关系  
 f ( n ) = \{ 停止 n = s t r . l e n g t h ( ) f ( n + 1 ) 0 ≤ n ≤ s t r . l e n g t h ( ) − 1 f(n) = \\begin\{cases\} 停止 & n = str.length() \\\\ f(n+1) & 0 \\leq n \\leq str.length() - 1 \\end\{cases\} f(n)=\{ 停止f(n\+1)n=str.length()0≤n≤str.length()−1  
代码为

public static void reversePrint(String str, int index) {
        
        if (index == str.length()) {
        
            return;
        }
        reversePrint(str, index + 1);
        System.out.println(str.charAt(index));
    }

拆解**伪码**如下，假设字符串为 “abc”

void reversePrint(String str, int index = 0) {
        
        void reversePrint(String str, int index = 1) {
        
            void reversePrint(String str, int index = 2) {
        
                void reversePrint(String str, int index = 3) {
         
                    if (index == str.length()) {
        
                        return; // 开始归
                    }
                }
                System.out.println(str.charAt(index)); // 打印 c
            }
            System.out.println(str.charAt(index)); // 打印 b
        }
        System.out.println(str.charAt(index)); // 打印 a
    }

#### 三、多路递归 Multi Recursion ####

**E01. 斐波那契数列**

*  之前的例子是每个递归函数只包含一个自身的调用，这称之为 single recursion
 *  如果每个递归函数例包含多个自身调用，称之为 multi recursion

**递推关系**  
 f ( n ) = \{ 0 n = 0 1 n = 1 f ( n − 1 ) + f ( n − 2 ) n > 1 f(n) = \\begin\{cases\} 0 & n=0 \\\\ 1 & n=1 \\\\ f(n-1) + f(n-2) & n>1 \\end\{cases\} f(n)=⎩⎨⎧01f(n−1)\+f(n−2)n=0n=1n>1

下面的表格列出了数列的前几项

**实现**

public static int f(int n) {
        
        if (n == 0) {
        
            return 0;
        }
        if (n == 1) {
        
            return 1;
        }
        return f(n - 1) + f(n - 2);
    }

**执行流程**

![08adde4753520e9be2ae9947b558f28f.gif][]

*  绿色代表正在执行（对应递），灰色代表执行结束（对应归）
 *  递不到头，不能归，对应着深度优先搜索

**时间复杂度**

*  递归的次数也符合斐波那契规律， 2 ∗ f ( n + 1 ) − 1 2 \* f(n+1)-1 2∗f(n\+1)−1
 *  时间复杂度推导过程
    
     *  斐波那契通项公式  f ( n ) = 1 5 ∗ ( 1 + 5 2 n − 1 − 5 2 n ) f(n) = \\frac\{1\}\{\\sqrt\{5\}\}\*(\{\\frac\{1+\\sqrt\{5\}\}\{2\}\}^n - \{\\frac\{1-\\sqrt\{5\}\}\{2\}\}^n) f(n)=51∗(21\+5n−21−5n)
     *  简化为： f ( n ) = 1 2.236 ∗ ( 1.618 n − ( − 0.618 ) n ) f(n) = \\frac\{1\}\{2.236\}\*(\{1.618\}^n - \{(-0.618)\}^n) f(n)=2.2361∗(1.618n−(−0.618)n)
     *  带入递归次数公式  2 ∗ 1 2.236 ∗ ( 1.618 n + 1 − ( − 0.618 ) n + 1 ) − 1 2\*\\frac\{1\}\{2.236\}\*(\{1.618\}^\{n+1\} - \{(-0.618)\}^\{n+1\})-1 2∗2.2361∗(1.618n\+1−(−0.618)n\+1)−1
     *  时间复杂度为  Θ ( 1.61 8 n ) \\Theta(1.618^n) Θ(1.618n)

> 1.  更多 Fibonacci 参考\[8\]\[9\]\[^10\]
> 2.  以上时间复杂度分析，未考虑大数相加的因素

**变体1 - 兔子问题\[^8\]**

![image-20221110155655827][]

*  第一个月，有一对未成熟的兔子（黑色，注意图中个头较小）
 *  第二个月，它们成熟
 *  第三个月，它们能产下一对新的小兔子（蓝色）
 *  所有兔子遵循相同规律，求第  n n n 个月的兔子数

**分析**

兔子问题如何与斐波那契联系起来呢？设第 n 个月兔子数为  f ( n ) f(n) f(n)

*   f ( n ) f(n) f(n) = 上个月兔子数 + 新生的小兔子数
 *  而【新生的小兔子数】实际就是【上个月成熟的兔子数】
 *  因为需要一个月兔子就成熟，所以【上个月成熟的兔子数】也就是【上上个月的兔子数】
 *  上个月兔子数，即  f ( n − 1 ) f(n-1) f(n−1)
 *  上上个月的兔子数，即  f ( n − 2 ) f(n-2) f(n−2)

因此本质还是斐波那契数列，只是从其第一项开始

**变体2 - 青蛙爬楼梯**

*  楼梯有  n n n 阶
 *  青蛙要爬到楼顶，可以一次跳一阶，也可以一次跳两阶
 *  只能向上跳，问有多少种跳法

**分析**

<table> 
 <thead> 
  <tr> 
   <th>n</th> 
   <th>跳法</th> 
   <th>规律</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>(1)</td> 
   <td>暂时看不出</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>(1,1) (2)</td> 
   <td>暂时看不出</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>(1,1,1) (1,2) (2,1)</td> 
   <td>暂时看不出</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>(1,1,1,1) (1,2,1) (2,1,1)<br>(1,1,2) (2,2)</td> 
   <td>最后一跳，跳一个台阶的，基于f(3)<br>最后一跳，跳两个台阶的，基于f(2)</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>…</td> 
   <td>…</td> 
  </tr> 
 </tbody> 
</table>

*  因此本质上还是斐波那契数列，只是从其第二项开始
 *  对应 leetcode 题目 [70. 爬楼梯 - 力扣（LeetCode）][70. _ - _LeetCode]

#### 四、递归优化-记忆法 ####

上述代码存在很多重复的计算，例如求  f ( 5 ) f(5) f(5) 递归分解过程

![image-20221207092417933][]

可以看到（颜色相同的是重复的）：

*   f ( 3 ) f(3) f(3) 重复了 2 次
 *   f ( 2 ) f(2) f(2) 重复了 3 次
 *   f ( 1 ) f(1) f(1) 重复了 5 次
 *   f ( 0 ) f(0) f(0) 重复了 3 次

随着  n n n 的增大，重复次数非常可观，如何优化呢？

**Memoization** 记忆法（也称备忘录）是一种优化技术，通过存储函数调用结果（通常比较昂贵），当再次出现相同的输入（子问题）时，就能实现加速效果，改进后的代码

public static void main(String[] args) {
        
        int n = 13;
        int[] cache = new int[n + 1];
        Arrays.fill(cache, -1);
        cache[0] = 0;
        cache[1] = 1;
        System.out.println(f(cache, n));
    }
    
    public static int f(int[] cache, int n) {
        
        if (cache[n] != -1) {
        
            return cache[n];
        }
    
        cache[n] = f(cache, n - 1) + f(cache, n - 2);
        return cache[n];
    }

优化后的图示，只要结果被缓存，就**不会执行其子问题**

![image-20221213173225807][]

*  改进后的时间复杂度为  O ( n ) O(n) O(n)
 *  请自行验证改进后的效果
 *  请自行分析改进后的空间复杂度

> **注意**
> 
> 1.  记忆法是动态规划的一种情况，强调的是自顶向下的解决
> 2.  记忆法的本质是空间换时间

#### 五、递归优化-尾递归 ####

**爆栈**

用递归做  n + ( n − 1 ) + ( n − 2 ) . . . + 1 n + (n-1) + (n-2) ... + 1 n\+(n−1)\+(n−2)...\+1

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

在我的机器上  n = 12000 n = 12000 n=12000 时，爆栈了

Exception in thread "main" java.lang.StackOverflowError
    	at Test.sum(Test.java:10)
    	at Test.sum(Test.java:10)
    	at Test.sum(Test.java:10)
    	at Test.sum(Test.java:10)
    	at Test.sum(Test.java:10)
    	...

为什么呢？

*  每次方法调用是需要消耗一定的栈内存的，这些内存用来存储方法参数、方法内局部变量、返回地址等等
 *  方法调用占用的内存需要等到**方法结束时**才会释放
 *  而递归调用我们之前讲过，不到最深不会回头，最内层方法没完成之前，外层方法都结束不了
    
     *  例如， s u m ( 3 ) sum(3) sum(3) 这个方法内有个需要执行  3 + s u m ( 2 ) 3 + sum(2) 3\+sum(2)， s u m ( 2 ) sum(2) sum(2) 没返回前，加号前面的  3 3 3 不能释放
     *  看下面伪码

long sum(long n = 3) {
        
        return 3 + long sum(long n = 2) {
        
            return 2 + long sum(long n = 1) {
        
                return 1;
            }
        }
    }

**尾调用**

如果函数的最后一步是调用一个函数，那么称为尾调用，例如

function a() {
        
        return b()
    }

下面三段代码**不能**叫做尾调用

function a() {
        
        const c = b()
        return c
    }

*  因为最后一步并非调用函数

function a() {
        
        return b() + 1
    }

*  最后一步执行的是加法

function a(x) {
        
        return b() + x
    }

*  最后一步执行的是加法

**一些语言**\[^11\]的编译器能够对尾调用做优化，例如

function a() {
        
        // 做前面的事
        return b() 
    }
    
    function b() {
        
        // 做前面的事
        return c()
    }
    
    function c() {
        
        return 1000
    }
    
    a()

没优化之前的**伪码**

function a() {
        
        return function b() {
        
            return function c() {
        
                return 1000
            }
        }
    }

优化后**伪码**如下

a()
    b()
    c()

为何尾递归才能优化？

调用 a 时

*  a 返回时发现：没什么可留给 b 的，将来返回的结果 b 提供就可以了，用不着我 a 了，我的内存就可以释放

调用 b 时

*  b 返回时发现：没什么可留给 c 的，将来返回的结果 c 提供就可以了，用不着我 b 了，我的内存就可以释放

如果调用 a 时

*  不是尾调用，例如 return b() + 1，那么 a 就不能提前结束，因为它还得利用 b 的结果做加法

**尾递归**

尾递归是尾调用的一种特例，也就是最后一步执行的是同一个函数

**尾递归避免爆栈**

安装 Scala

![image-20221111122709227][]

Scala 入门

object Main {
        
      def main(args: Array[String]): Unit = {
        
        println("Hello Scala")
      }
    }

*  Scala 是 java 的近亲，java 中的类都可以拿来重用
 *  类型是放在变量后面的
 *  Unit 表示无返回值，类似于 void
 *  不需要以分号作为结尾，当然加上也对

还是先写一个会爆栈的函数

def sum(n: Long): Long = {
        
        if (n == 1) {
        
            return 1
        }
        return n + sum(n - 1)
    }

*  Scala 最后一行代码若作为返回值，可以省略 return

不出所料，在  n = 11000 n = 11000 n=11000 时，还是出了异常

println(sum(11000))
    
    Exception in thread "main" java.lang.StackOverflowError
    	at Main$.sum(Main.scala:25)
    	at Main$.sum(Main.scala:25)
    	at Main$.sum(Main.scala:25)
    	at Main$.sum(Main.scala:25)
    	...

这是因为以上代码，还不是尾调用，要想成为尾调用，那么：

1.  最后一行代码，必须是一次函数调用
2.  内层函数必须**摆脱**与外层函数的关系，内层函数**执行后**不依赖于外层的变量或常量

def sum(n: Long): Long = {
        
        if (n == 1) {
        
            return 1
        }
        return n + sum(n - 1)  // 依赖于外层函数的 n 变量
    }

如何让它执行后就摆脱对 n 的依赖呢？

*  不能等递归回来再做加法，那样就必须保留外层的 n
 *  把 n 当做内层函数的一个参数传进去，这时 n 就属于内层函数了
 *  传参时就完成累加, 不必等回来时累加

sum(n - 1, n + 累加器)

改写后代码如下

@tailrec
    def sum(n: Long, accumulator: Long): Long = {
        
        if (n == 1) {
        
            return 1 + accumulator
        } 
        return sum(n - 1, n + accumulator)
    }

*  accumulator 作为累加器
 *  @tailrec 注解是 scala 提供的，用来检查方法是否符合尾递归
 *  这回 sum(10000000, 0) 也没有问题，打印 50000005000000

执行流程如下，以**伪码**表示  s u m ( 4 , 0 ) sum(4, 0) sum(4,0)

// 首次调用
    def sum(n = 4, accumulator = 0): Long = {
        
        return sum(4 - 1, 4 + accumulator)
    }
    
    // 接下来调用内层 sum, 传参时就完成了累加, 不必等回来时累加，当内层 sum 调用后，外层 sum 空间没必要保留
    def sum(n = 3, accumulator = 4): Long = {
        
        return sum(3 - 1, 3 + accumulator)
    }
    
    // 继续调用内层 sum
    def sum(n = 2, accumulator = 7): Long = {
        
        return sum(2 - 1, 2 + accumulator)
    }
    
    // 继续调用内层 sum, 这是最后的 sum 调用完就返回最后结果 10, 前面所有其它 sum 的空间早已释放
    def sum(n = 1, accumulator = 9): Long = {
        
        if (1 == 1) {
        
            return 1 + accumulator
        }
    }

本质上，尾递归优化是将函数的**递归**调用，变成了函数的**循环**调用

**改循环避免爆栈**

public static void main(String[] args) {
        
        long n = 100000000;
        long sum = 0;
        for (long i = n; i >= 1; i--) {
        
            sum += i;
        }
        System.out.println(sum);
    }

#### 六、递归时间复杂度-Master theorem\[^14\] ####

若有递归式  
 T ( n ) = a T ( n b ) + f ( n ) T(n) = aT(\\frac\{n\}\{b\}) + f(n) T(n)=aT(bn)\+f(n)  
其中

*   T ( n ) T(n) T(n) 是问题的运行时间， n n n 是数据规模
 *   a a a 是子问题个数
 *   T ( n b ) T(\\frac\{n\}\{b\}) T(bn) 是子问题运行时间，每个子问题被拆成原问题数据规模的  n b \\frac\{n\}\{b\} bn
 *   f ( n ) f(n) f(n) 是除递归外执行的计算

令  x = log ⁡ b a x = \\log\_\{b\}\{a\} x=logba，即  x = log ⁡ 子问题缩小倍数 子问题个数 x = \\log\_\{子问题缩小倍数\}\{子问题个数\} x=log子问题缩小倍数子问题个数

那么  
 T ( n ) = \{ Θ ( n x ) f ( n ) = O ( n c ) 并且 c < x Θ ( n x log ⁡ n ) f ( n ) = Θ ( n x ) Θ ( n c ) f ( n ) = Ω ( n c ) 并且 c > x T(n) = \\begin\{cases\} \\Theta(n^x) & f(n) = O(n^c) 并且 c \\lt x\\\\ \\Theta(n^x\\log\{n\}) & f(n) = \\Theta(n^x)\\\\ \\Theta(n^c) & f(n) = \\Omega(n^c) 并且 c \\gt x \\end\{cases\} T(n)=⎩⎨⎧Θ(nx)Θ(nxlogn)Θ(nc)f(n)=O(nc)并且c<xf(n)=Θ(nx)f(n)=Ω(nc)并且c>x

**例1**

T ( n ) = 2 T ( n 2 ) + n 4 T(n) = 2T(\\frac\{n\}\{2\}) + n^4 T(n)=2T(2n)\+n4

*  此时  x = 1 < 4 x = 1 < 4 x=1<4，由后者决定整个时间复杂度  Θ ( n 4 ) \\Theta(n^4) Θ(n4)
 *  如果觉得对数不好算，可以换为求【 b b b 的几次方能等于  a a a】

**例2**

T ( n ) = T ( 7 n 10 ) + n T(n) = T(\\frac\{7n\}\{10\}) + n T(n)=T(107n)\+n

*   a = 1 , b = 10 7 , x = 0 , c = 1 a=1, b=\\frac\{10\}\{7\}, x=0, c=1 a=1,b=710,x=0,c=1
 *  此时  x = 0 < 1 x = 0 < 1 x=0<1，由后者决定整个时间复杂度  Θ ( n ) \\Theta(n) Θ(n)

**例3**

T ( n ) = 16 T ( n 4 ) + n 2 T(n) = 16T(\\frac\{n\}\{4\}) + n^2 T(n)=16T(4n)\+n2

*   a = 16 , b = 4 , x = 2 , c = 2 a=16, b=4, x=2, c=2 a=16,b=4,x=2,c=2
 *  此时  x = 2 = c x=2 = c x=2=c，时间复杂度  Θ ( n 2 log ⁡ n ) \\Theta(n^2 \\log\{n\}) Θ(n2logn)

**例4**

T ( n ) = 7 T ( n 3 ) + n 2 T(n)=7T(\\frac\{n\}\{3\}) + n^2 T(n)=7T(3n)\+n2

*   a = 7 , b = 3 , x = 1. ? , c = 2 a=7, b=3, x=1.?, c=2 a=7,b=3,x=1.?,c=2
 *  此时  x = log ⁡ 3 7 < 2 x = \\log\_\{3\}\{7\} < 2 x=log37<2，由后者决定整个时间复杂度  Θ ( n 2 ) \\Theta(n^2) Θ(n2)

**例5**

T ( n ) = 7 T ( n 2 ) + n 2 T(n) = 7T(\\frac\{n\}\{2\}) + n^2 T(n)=7T(2n)\+n2

*   a = 7 , b = 2 , x = 2. ? , c = 2 a=7, b=2, x=2.?, c=2 a=7,b=2,x=2.?,c=2
 *  此时  x = l o g 2 7 > 2 x = log\_2\{7\} > 2 x=log27>2，由前者决定整个时间复杂度  Θ ( n log ⁡ 2 7 ) \\Theta(n^\{\\log\_2\{7\}\}) Θ(nlog27)

**例6**

T ( n ) = 2 T ( n 4 ) + n T(n) = 2T(\\frac\{n\}\{4\}) + \\sqrt\{n\} T(n)=2T(4n)\+n

*   a = 2 , b = 4 , x = 0.5 , c = 0.5 a=2, b=4, x = 0.5, c=0.5 a=2,b=4,x=0.5,c=0.5
 *  此时  x = 0.5 = c x = 0.5 = c x=0.5=c，时间复杂度  Θ ( n log ⁡ n ) \\Theta(\\sqrt\{n\}\\ \\log\{n\}) Θ(nlogn)

**例7. 二分查找递归**

int f(int[] a, int target, int i, int j) {
        
        if (i > j) {
        
            return -1;
        }
        int m = (i + j) >>> 1;
        if (target < a[m]) {
        
            return f(a, target, i, m - 1);
        } else if (a[m] < target) {
        
            return f(a, target, m + 1, j);
        } else {
        
            return m;
        }
    }

*  子问题个数  a = 1 a = 1 a=1
 *  子问题数据规模缩小倍数  b = 2 b = 2 b=2
 *  除递归外执行的计算是常数级  c = 0 c=0 c=0

T ( n ) = T ( n 2 ) + n 0 T(n) = T(\\frac\{n\}\{2\}) + n^0 T(n)=T(2n)\+n0

*  此时  x = 0 = c x=0 = c x=0=c，时间复杂度  Θ ( log ⁡ n ) \\Theta(\\log\{n\}) Θ(logn)

**例8. 归并排序递归**

void split(B[], i, j, A[])
    {
        
        if (j - i <= 1)                    
            return;                                
        m = (i + j) / 2;             
        
        // 递归
        split(A, i, m, B);  
        split(A, m, j, B); 
        
        // 合并
        merge(B, i, m, j, A);
    }

*  子问题个数  a = 2 a=2 a=2
 *  子问题数据规模缩小倍数  b = 2 b=2 b=2
 *  除递归外，主要时间花在合并上，它可以用  f ( n ) = n f(n) = n f(n)=n 表示

T ( n ) = 2 T ( n 2 ) + n T(n) = 2T(\\frac\{n\}\{2\}) + n T(n)=2T(2n)\+n

*  此时  x = 1 = c x=1=c x=1=c，时间复杂度  Θ ( n log ⁡ n ) \\Theta(n\\log\{n\}) Θ(nlogn)

**例9. 快速排序递归**

algorithm quicksort(A, lo, hi) is 
      if lo >= hi || lo < 0 then 
        return
      
      // 分区
      p := partition(A, lo, hi) 
      
      // 递归
      quicksort(A, lo, p - 1) 
      quicksort(A, p + 1, hi)

*  子问题个数  a = 2 a=2 a=2
 *  子问题数据规模缩小倍数
    
     *  如果分区分的好， b = 2 b=2 b=2
     *  如果分区没分好，例如分区1 的数据是 0，分区 2 的数据是  n − 1 n-1 n−1
 *  除递归外，主要时间花在分区上，它可以用  f ( n ) = n f(n) = n f(n)=n 表示

情况1 - 分区分的好

T ( n ) = 2 T ( n 2 ) + n T(n) = 2T(\\frac\{n\}\{2\}) + n T(n)=2T(2n)\+n

*  此时  x = 1 = c x=1=c x=1=c，时间复杂度  Θ ( n log ⁡ n ) \\Theta(n\\log\{n\}) Θ(nlogn)

情况2 - 分区没分好

T ( n ) = T ( n − 1 ) + T ( 1 ) + n T(n) = T(n-1) + T(1) + n T(n)=T(n−1)\+T(1)\+n

*  此时不能用主定理求解

#### 七、递归时间复杂度-展开求解 ####

像下面的递归式，都不能用主定理求解

**例1 - 递归求和**

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

T ( n ) = T ( n − 1 ) + c T(n) = T(n-1) + c T(n)=T(n−1)\+c， T ( 1 ) = c T(1) = c T(1)=c

下面为展开过程

T ( n ) = T ( n − 2 ) + c + c T(n) = T(n-2) + c + c T(n)=T(n−2)\+c\+c

T ( n ) = T ( n − 3 ) + c + c + c T(n) = T(n-3) + c + c + c T(n)=T(n−3)\+c\+c\+c

…

T ( n ) = T ( n − ( n − 1 ) ) + ( n − 1 ) c T(n) = T(n-(n-1)) + (n-1)c T(n)=T(n−(n−1))\+(n−1)c

*  其中  T ( n − ( n − 1 ) ) T(n-(n-1)) T(n−(n−1)) 即  T ( 1 ) T(1) T(1)
 *  带入求得  T ( n ) = c + ( n − 1 ) c = n c T(n) = c + (n-1)c = nc T(n)=c\+(n−1)c=nc

时间复杂度为  O ( n ) O(n) O(n)

**例2 - 递归冒泡排序**

void bubble(int[] a, int high) {
        
        if(0 == high) {
        
            return;
        }
        for (int i = 0; i < high; i++) {
        
            if (a[i] > a[i + 1]) {
        
                swap(a, i, i + 1);
            }
        }
        bubble(a, high - 1);
    }

T ( n ) = T ( n − 1 ) + n T(n) = T(n-1) + n T(n)=T(n−1)\+n， T ( 1 ) = c T(1) = c T(1)=c

下面为展开过程

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

T ( n ) = T ( n − 3 ) + ( n − 2 ) + ( n − 1 ) + n T(n) = T(n-3) + (n-2) + (n-1) + n T(n)=T(n−3)\+(n−2)\+(n−1)\+n

…

T ( n ) = T ( 1 ) + 2 + . . . + n = T ( 1 ) + ( n − 1 ) 2 + n 2 = c + n 2 2 + n 2 − 1 T(n) = T(1) + 2 + ... + n = T(1) + (n-1)\\frac\{2+n\}\{2\} = c + \\frac\{n^2\}\{2\} + \\frac\{n\}\{2\} -1 T(n)=T(1)\+2\+...\+n=T(1)\+(n−1)22\+n=c\+2n2\+2n−1

时间复杂度  O ( n 2 ) O(n^2) O(n2)

> 注：
> 
>  *  等差数列求和为  个数 ∗ ∣ 首项 − 末项 ∣ 2 个数\*\\frac\{\\vert首项-末项\\vert\}\{2\} 个数∗2∣首项−末项∣

**例3 - 递归快排**

快速排序分区没分好的极端情况

T ( n ) = T ( n − 1 ) + T ( 1 ) + n T(n) = T(n-1) + T(1) + n T(n)=T(n−1)\+T(1)\+n， T ( 1 ) = c T(1) = c T(1)=c

T ( n ) = T ( n − 1 ) + c + n T(n) = T(n-1) + c + n T(n)=T(n−1)\+c\+n

下面为展开过程

T ( n ) = T ( n − 2 ) + c + ( n − 1 ) + c + n T(n) = T(n-2) + c + (n-1) + c + n T(n)=T(n−2)\+c\+(n−1)\+c\+n

T ( n ) = T ( n − 3 ) + c + ( n − 2 ) + c + ( n − 1 ) + c + n T(n) = T(n-3) + c + (n-2) + c + (n-1) + c + n T(n)=T(n−3)\+c\+(n−2)\+c\+(n−1)\+c\+n

…

T ( n ) = T ( n − ( n − 1 ) ) + ( n − 1 ) c + 2 + . . . + n = n 2 2 + 2 c n + n 2 − 1 T(n) = T(n-(n-1)) + (n-1)c + 2+...+n = \\frac\{n^2\}\{2\} + \\frac\{2cn+n\}\{2\} -1 T(n)=T(n−(n−1))\+(n−1)c\+2\+...\+n=2n2\+22cn\+n−1

时间复杂度  O ( n 2 ) O(n^2) O(n2)

不会推导的同学可以进入 https://www.wolframalpha.com/

*  例1 输入 f(n) = f(n - 1) + c, f(1) = c
 *  例2 输入 f(n) = f(n - 1) + n, f(1) = c
 *  例3 输入 f(n) = f(n - 1) + n + c, f(1) = c

###  ###

if (a[i] > a[i + 1]) {
            swap(a, i, i + 1);
        }
    }
    bubble(a, high - 1);

$T(n) = T(n-1) + n$，$T(1) = c$
    
    下面为展开过程
    
    $T(n) = T(n-2) + (n-1) + n$
    
    $T(n) = T(n-3) + (n-2) + (n-1) + n$
    
    ...
    
    $T(n) = T(1) + 2 + ... + n = T(1) + (n-1)\frac{2+n}{2} = c + \frac{n^2}{2} + \frac{n}{2} -1$
    
    时间复杂度 $O(n^2)$
    
    > 注：
    >
    > * 等差数列求和为 $个数*\frac{\vert首项-末项\vert}{2}$ 
    
    
    
    **例3 - 递归快排**
    
    快速排序分区没分好的极端情况
    
    $T(n) = T(n-1) + T(1) + n$，$T(1) = c$
    
    $T(n) = T(n-1) + c + n$
    
    下面为展开过程
    
    $T(n) = T(n-2) + c + (n-1) + c + n$
    
    $T(n) = T(n-3) + c + (n-2) + c + (n-1) + c + n$
    
    ...
    
    $T(n) = T(n-(n-1)) + (n-1)c + 2+...+n = \frac{n^2}{2} + \frac{2cn+n}{2} -1$
    
    时间复杂度 $O(n^2)$
    
    
    
    不会推导的同学可以进入 https://www.wolframalpha.com/
    
    * 例1 输入 f(n) = f(n - 1) + c, f(1) = c
    * 例2 输入 f(n) = f(n - 1) + n, f(1) = c
    * 例3 输入 f(n) = f(n - 1) + n + c, f(1) = c
    
    
    
    ##

[ea689b325bd64e3d99e44e943c5dbdb3.png]: https://img-blog.csdnimg.cn/ea689b325bd64e3d99e44e943c5dbdb3.png
[08adde4753520e9be2ae9947b558f28f.gif]: https://img-blog.csdnimg.cn/img_convert/08adde4753520e9be2ae9947b558f28f.gif
[image-20221110155655827]: https://img-blog.csdnimg.cn/img_convert/2d46f859396efa0ffd0a874df07ac9a3.png
[70. _ - _LeetCode]: https://leetcode.cn/problems/climbing-stairs/
[image-20221207092417933]: https://img-blog.csdnimg.cn/img_convert/6514e8b885b70ad49775797f773e12bb.png
[image-20221213173225807]: https://img-blog.csdnimg.cn/img_convert/aeedc1b9b3fbab6a52de58b0b64421e9.png
[image-20221111122709227]: https://img-blog.csdnimg.cn/img_convert/44f132d417dd56716e04bf5dae144265.png