深入理解递归算法

概述
定义

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

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
4
5
6
7
8
说明：

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

假设链表中有 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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
思路

确定能否使用递归求解
推导出递推关系，即父问题与子问题的关系，以及递归的结束条件
例如之前遍历链表的递推关系为
f ( n ) = { 停止 n = n u l l f ( n . n e x t ) n ≠ n u l l f(n) =
{停止f(n.next)n=nulln≠null
{停止n=nullf(n.next)n≠null
f(n)={
停止
f(n.next)
​

n=null
n

=null
​

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

阶乘的定义 n ! = 1 ⋅ 2 ⋅ 3 ⋯ ( n − 2 ) ⋅ ( n − 1 ) ⋅ n n!= 1⋅2⋅3⋯(n-2)⋅(n-1)⋅nn!=1⋅2⋅3⋯(n−2)⋅(n−1)⋅n，其中 n nn 为自然数，当然 0 ! = 1 0! = 10!=1

递推关系

f ( n ) = { 1 n = 1 n ∗ f ( n − 1 ) n > 1 f(n) =
{1n∗f(n−1)n=1n>1
{1n=1n∗f(n−1)n>1
f(n)={
1
n∗f(n−1)
​

n=1
n>1
​

代码

private static int f(int n) {
if (n == 1) {
return 1;
}
return n * f(n - 1);
}
1
2
3
4
5
6
拆解伪码如下，假设 n 初始值为 3

f(int n = 3) { // 解决不了,递
return 3 f(int n = 2) { // 解决不了,继续递
return 2 f(int n = 1) {
if (n == 1) { // 可以解决, 开始归
return 1;
}
}
}
}
1
2
3
4
5
6
7
8
9
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) =
{停止f(n+1)n=str.length()0≤n≤str.length()−1
{停止n=str.length()f(n+1)0≤n≤str.length()−1
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));
}
1
2
3
4
5
6
7
拆解伪码如下，假设字符串为 “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
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
E03. 二分查找
递归关系：

代码实现：

//使用递归实现二分查找（搜索范围：闭区间）
public static void binarySearch(int[] nums,int target,int start,int end){

    if (start > end) return;

    int middle = (start + end) / 2;

    if (nums[middle] < target) binarySearch(nums,target,middle + 1,end);
    else if (nums[middle] > target) binarySearch(nums,target,start,middle - 1);
    else System.out.println(target + "的索引为：" + middle);
}

1
2
3
4
5
6
7
8
9
10
11
多路递归 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) =
⎧⎩⎨01f(n−1)+f(n−2)n=0n=1n>1
{0n=01n=1f(n−1)+f(n−2)n>1
f(n)=
⎩
⎨
⎧
​

0
1
f(n−1)+f(n−2)
​

n=0
n=1
n>1
​

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

F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13
0 1 1 2 3 5 8 13 21 34 55 89 144 233
实现

public static int f(int n) {
if (n == 0) {
return 0;
}
if (n == 1) {
return 1;
}
return f(n - 1) + f(n - 2);
}
1
2
3
4
5
6
7
8
9
执行流程

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

递归的次数也符合斐波那契规律，2 ∗ f ( n + 1 ) − 1 2 f(n+1)-12∗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)=
5
​

1
​
∗(
2
1+
5
​

​

n
−
2
1−
5
​

​

n
)
简化为：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.236
1
​
∗(1.618
n
−(−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})-12∗
2.236
1
​
∗(1.618
n+1
−(−0.618)
n+1
)−1
时间复杂度为 Θ ( 1.61 8 n ) \Theta(1.618^n)Θ(1.618
n
)
以上时间复杂度分析，未考虑大数相加的因素

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

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

兔子问题如何与斐波那契联系起来呢？设第 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 nn 阶
青蛙要爬到楼顶，可以一次跳一阶，也可以一次跳两阶
只能向上跳，问有多少种跳法
分析

n 跳法 规律
1 (1) 暂时看不出
2 (1,1) (2) 暂时看不出
3 (1,1,1) (1,2) (2,1) 暂时看不出
4 (1,1,1,1) (1,2,1) (2,1,1)
(1,1,2) (2,2) 最后一跳，跳一个台阶的，基于f(3)
最后一跳，跳两个台阶的，基于f(2)
5 … …
因此本质上还是斐波那契数列，只是从其第二项开始

对应 leetcode 题目 70. 爬楼梯 - 力扣（LeetCode）

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

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

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 nn 的增大，重复次数非常可观，如何优化呢？

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];

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
优化后的图示，只要结果被缓存，就不会执行其子问题

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

记忆法是动态规划的一种情况，强调的是自顶向下的解决
记忆法的本质是空间换时间
递归优化-尾递归
爆栈

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

public static long sum(long n) {
if (n == 1) {
return 1;
}
return n + sum(n - 1);
}
1
2
3
4
5
6
在我的机器上 n = 12000 n = 12000n=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)
...
1
2
3
4
5
6
7
为什么呢？

每次方法调用是需要消耗一定的栈内存的，这些内存用来存储方法参数、方法内局部变量、返回地址等等
方法调用占用的内存需要等到方法结束时才会释放
而递归调用我们之前讲过，不到最深不会回头，最内层方法没完成之前，外层方法都结束不了
例如，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 33 不能释放
看下面伪码
long sum(long n = 3) {
return 3 + long sum(long n = 2) {
return 2 + long sum(long n = 1) {
return 1;
}
}
}
1
2
3
4
5
6
7
尾调用

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

function a() {
return b()
}
1
2
3
下面三段代码不能叫做尾调用

function a() {
const c = b()
return c
}
1
2
3
4
因为最后一步并非调用函数
function a() {
return b() + 1
}
1
2
3
最后一步执行的是加法
function a(x) {
return b() + x
}
1
2
3
最后一步执行的是加法
一些语言[^11]的编译器能够对尾调用做优化，例如

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

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

function c() {
return 1000
}

a()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
没优化之前的伪码

function a() {
return function b() {
return function c() {
return 1000
}
}
}
1
2
3
4
5
6
7
优化后伪码如下

a()
b()
c()
1
2
3
为何尾递归才能优化？

调用 a 时

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

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

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

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

尾递归避免爆栈

安装 Scala

Scala 入门

object Main {
def main(args: Array[String]): Unit = {
println("Hello Scala")
}
}
1
2
3
4
5
Scala 是 java 的近亲，java 中的类都可以拿来重用
类型是放在变量后面的
Unit 表示无返回值，类似于 void
不需要以分号作为结尾，当然加上也对
还是先写一个会爆栈的函数

def sum(n: Long): Long = {
if (n == 1) {
return 1
}
return n + sum(n - 1)
}
1
2
3
4
5
6
Scala 最后一行代码若作为返回值，可以省略 return
不出所料，在 n = 11000 n = 11000n=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
3
4
5
6
7
8
这是因为以上代码，还不是尾调用，要想成为尾调用，那么：

最后一行代码，必须是一次函数调用
内层函数必须摆脱与外层函数的关系，内层函数执行后不依赖于外层的变量或常量
def sum(n: Long): Long = {
if (n == 1) {
return 1
}
return n + sum(n - 1) // 依赖于外层函数的 n 变量
}
1
2
3
4
5
6
如何让它执行后就摆脱对 n 的依赖呢？

不能等递归回来再做加法，那样就必须保留外层的 n
把 n 当做内层函数的一个参数传进去，这时 n 就属于内层函数了
传参时就完成累加, 不必等回来时累加
sum(n - 1, n + 累加器)
1
改写后代码如下

@tailrec
def sum(n: Long, accumulator: Long): Long = {
if (n == 1) {
return 1 + accumulator
}
return sum(n - 1, n + accumulator)
}
1
2
3
4
5
6
7
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
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
本质上，尾递归优化是将函数的递归调用，变成了函数的循环调用

改循环避免爆栈

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);
}
1
2
3
4
5
6
7
8
递归时间复杂度-Master theorem
若有递归式
T ( n ) = a T ( n b ) + f ( n ) T(n) = aT(\frac{n}{b}) + f(n)
T(n)=aT(
b
n
​
)+f(n)

其中

T ( n ) T(n)T(n) 是问题的运行时间，n nn 是数据规模
a aa 是子问题个数
T ( n b ) T(\frac{n}{b})T(
b
n
​
) 是子问题运行时间，每个子问题被拆成原问题数据规模的 n b \frac{n}{b}
b
n
​

f ( n ) f(n)f(n) 是除递归外执行的计算
令 x = log ⁡ b a x = \log{b}{a}x=log
b
​
a，即 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) =
⎧⎩⎨Θ(nx)Θ(nxlogn)Θ(nc)f(n)=O(nc)并且cx
{Θ(nx)f(n)=O(nc)并且cx
T(n)=
⎩
⎨
⎧
​

Θ(n
x
)
Θ(n
x
logn)
Θ(n
c
)
​

f(n)=O(n
c
)并且cx
​

例1

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

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

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

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

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

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

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

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

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

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

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

a = 2 , b = 4 , x = 0.5 , c = 0.5 a=2, b=4, x = 0.5, c=0.5a=2,b=4,x=0.5,c=0.5
此时 x = 0.5 = c x = 0.5 = cx=0.5=c，时间复杂度 Θ ( n log ⁡ n ) \Theta(\sqrt{n}\ \log{n})Θ(
n
​
logn)
例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;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
子问题个数 a = 1 a = 1a=1
子问题数据规模缩小倍数 b = 2 b = 2b=2
除递归外执行的计算是常数级 c = 0 c=0c=0
T ( n ) = T ( n 2 ) + n 0 T(n) = T(\frac{n}{2}) + n^0T(n)=T(
2
n
​
)+n
0

此时 x = 0 = c x=0 = cx=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);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
子问题个数 a = 2 a=2a=2
子问题数据规模缩小倍数 b = 2 b=2b=2
除递归外，主要时间花在合并上，它可以用 f ( n ) = n f(n) = nf(n)=n 表示
T ( n ) = 2 T ( n 2 ) + n T(n) = 2T(\frac{n}{2}) + nT(n)=2T(
2
n
​
)+n

此时 x = 1 = c x=1=cx=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)
1
2
3
4
5
6
7
8
9
10
子问题个数 a = 2 a=2a=2
子问题数据规模缩小倍数
如果分区分的好，b = 2 b=2b=2
如果分区没分好，例如分区1 的数据是 0，分区 2 的数据是 n − 1 n-1n−1
除递归外，主要时间花在分区上，它可以用 f ( n ) = n f(n) = nf(n)=n 表示
情况1 - 分区分的好

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

此时 x = 1 = c x=1=cx=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) + nT(n)=T(n−1)+T(1)+n

此时不能用主定理求解
递归时间复杂度-展开求解
像下面的递归式，都不能用主定理求解

例1 - 递归求和

long sum(long n) {
if (n == 1) {
return 1;
}
return n + sum(n - 1);
}
1
2
3
4
5
6
T ( n ) = T ( n − 1 ) + c T(n) = T(n-1) + cT(n)=T(n−1)+c，T ( 1 ) = c T(1) = cT(1)=c

下面为展开过程

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

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

…

T ( n ) = T ( n − ( n − 1 ) ) + ( n − 1 ) c T(n) = T(n-(n-1)) + (n-1)cT(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 = ncT(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);
}
1
2
3
4
5
6
7
8
9
10
11
T ( n ) = T ( n − 1 ) + n T(n) = T(n-1) + nT(n)=T(n−1)+n，T ( 1 ) = c T(1) = cT(1)=c

下面为展开过程

T ( n ) = T ( n − 2 ) + ( n − 1 ) + n T(n) = T(n-2) + (n-1) + nT(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) + nT(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} -1T(n)=T(1)+2+...+n=T(1)+(n−1)
2
2+n
​
=c+
2
n
2

​

• 2
  n
  ​
  −1

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

注：

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

例3 - 递归快排

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

T ( n ) = T ( n − 1 ) + T ( 1 ) + n T(n) = T(n-1) + T(1) + nT(n)=T(n−1)+T(1)+n，T ( 1 ) = c T(1) = cT(1)=c

T ( n ) = T ( n − 1 ) + c + n T(n) = T(n-1) + c + nT(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 + nT(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 + nT(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} -1T(n)=T(n−(n−1))+(n−1)c+2+...+n=
2
n
2

​

• 2
  2cn+n
  ​
  −1

时间复杂度 O ( n 2 ) O(n^2)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
————————————————
版权声明：本文为CSDN博主「十八岁讨厌编程」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/zyb18507175502/article/details/130708001