一、递归
1. 概述
定义：在计算机科学中，递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小子集。
比如单链表递归遍历的例子：
void f(Node node) {
if(node == null) {
return;
}
println("before:" + node.value)
f(node.next);
println("after:" + node.value)
}说明：
- 自己调用自己，如果说每个函数对应着一种解决方案，自己调用自己意味着解决方案是一样的（有规律的）
- 每次调用，函数处理的数据会较上次缩减（子集），而且最后会缩减至无需继续递归
- 内层函数调用（子集处理）完成，外层函数才能算调用完成
原理
假设链表中有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. 推导出递推关系，即父问题与子问题的关系，以及递归的结束条件
例如之前遍历链表的递推关系为
- 深入到最里层叫递
- 从最里层处理叫归
- 在递的过程中，外层函数内的局部变量（以及方法参数）并未消失，归的时候还可以用到
2. 单路递归Single Recursion
2.1 阶乘
用递归方法求阶乘
- 阶乘的定义：n! = 1 * 2 * 3 ... (n - 2) * (n - 1) * n，其中n为自然数，当然 0! = 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;
}
}
}
}2.1 反向打印字符串
用递归反向打印字符串，n 为字符在整个字符串 str 中的索引位置
-
递：n 从 0 开始，每次 n + 1，一直递到 n == str.length() - 1
-
归：从 n == str.length() 开始归，从归打印，自然是逆序的
递推关系
代码为
public static void reversePrint(String str, int index) {
if (index == str.length()) {
return;
}
reversePrint(str, index + 1);
System.out.println(str.charAt(index));
}2.2 二分查找（单路递归）
public static int binarySearch(int[] a, int target) {
return recursion(a, target, 0, a.length - 1);
}
public static int recursion(int[] a, int target, int i, int j) {
if (i > j) {
return -1;
}
int m = (i + j) >>> 1;
if (target < a[m]) {
return recursion(a, target, i, m - 1);
} else if (a[m] < target) {
return recursion(a, target, m + 1, j);
} else {
return m;
}
}2.3 冒泡排序（单路递归）
- 将数组划分为两部分[0 ... j] [j + 1 ... a.length - 1]
- 左边[0 ... j]是未排序部分
- 右边[j + 1 ... a.length - 1]是已排序部分
- 未排序区间内，相邻的两个元素比较，如果前一个大于后一个，则交换位置
public static void main(String[] args) {
int[] a = {3, 2, 6, 1, 5, 4, 7};
bubble(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
private static void bubble(int[] a, int low, int high) {
if(low == high) {
return;
}
int j = low;
for (int i = low; i < high; i++) {
if (a[i] > a[i + 1]) {
swap(a, i, i + 1);
j = i;
}
}
bubble(a, low, j);
}
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}- low与high为未排序范围
- j表示的是未排序的边界，下一次递归时的high
- 发生交换，意味着有无序情况
- 最后一次交换（以后没有无序）时，左侧i仍是无序，右侧i+1已然有序
private static void bubble(int[] a, int j) {
if (j == 0) {
return;
}
int x = 0; // x右侧的元素都是有序的
for(int i = 0; i < j; i++) {
{
if(a[i] > a[i + 1]) {
{
int t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
x = i;
}
}
bubble(a, x);
}C++版冒泡排序：exchange右侧都是有序的
#include<iostream>
#include<vector>
using namespace std;
void BubbleSort(vector<int>& data, int length){
int j, exchange, bound, temp;
exchange = length - 1; // 第一趟冒泡排序的区间是[0 ~ length - 1]
while(exchange != 0){
bound = exchange;
exchange = 0;
for(j = 0; j < bound; j++) // 一趟冒泡排序的区间是[0 ~ bound]
{
if(data[j] > data[j + 1]){
temp = data[j];
data[j] = data[j + 1];
data[j + 1] = temp;
exchange = j; // 记载每一次记录交换的位置
}
}
}
}2.4 插入排序（单路递归）
public static void main(String[] args) {
int[] a = {3, 2, 6, 1, 5, 7, 4};
insertion(a, 1, a.length - 1);
System.out.println(Arrays.toString(a));
}
private static void insertion(int[] a, int low, int high) {
if (low > high) {
return;
}
// low指针指的是未排序区的边界
int i = low - 1; // 已排序区的指针
int t = a[low];
while (i >= 0 && a[i] > t) { // 没有找到插入位置
a[i + 1] = a[i]; // 空出插入位置
i--;
}
if(i + 1 != low) {
a[i + 1] = t;
}
insertion(a, low + 1, high);
}public void insertionSort(int[] nums, int length) {
int i, j, temp;
for(i = 1; i < length; i++) {
temp = nums[i];
for(j = i - 1; j >= 0 && temp < nums[j]; j--) { // 寻找插入位置
nums[j + 1] = nums[j]; // 后移
}
nums[j + 1] = temp;
}
}2.5 约瑟夫问题（单路递归）
n个人排成圆圈，从头开始报数，每次数到第m个人杀之，继续从下一个人重复以上过程，求最后活下来的人是谁？
解法一：
设josephus(n, m)表示在n个人中，每m个人被杀时最后存活的人。递归关系为：
josephus(n, m) = (josephus(n - 1, m) + m) % n, n > 1
josephus(1, m) = 0
这个关系的意思是，若我们知道n-1个人时的存活者，我们可以通过调整索引来得出n个人时的存活者。
class Solution {
public int findTheWinner(int n, int m) {
return josephus(n, m) + 1; // 转换为1-based索引
}
private int josephus(int n, int m) {
if (n == 1) return 0; // 只有一个人时，返回其索引0
return (josephus(n - 1, m) + m) % n; // 递归公式
}
public static void main(String[] args) {
Solution solution = new Solution();
int n = 7; // 总人数
int m = 3; // 每次报数到m的人被杀
int winner = solution.findTheWinner(n, m);
System.out.println("最后存活下来的人的位置是: " + winner); // 输出最后存活者的1-based索引
}
}3 多路递归 Multi Recursion
如果每个递归函数例包含多个自身调用，称之为multi recursion
3.1 裴波那契数列
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
示例 2：
输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
提示：
1 <= n <= 45
Java实现
解法一：递归，会超时
class Solution {
public int climbStairs(int n) {
if(n == 1) {
return 1;
}
if(n == 2) {
return 2;
}
return climbStairs(n - 1) + climbStairs(n - 2);
}
}递归的次数也符合斐波那契数列规律：2 * f(n + 1) - 1
时间复杂度推导过程：
解法二：
class Solution {
public int climbStairs(int n) {
if(n == 1) {
return 1;
}
if(n == 2) {
return 2;
}
int prev = 1;
int curr = 2;
for(int i = 3; i <= n; i++) {
int temp = curr;
curr = prev + curr;
prev = temp;
}
return curr;
}
}3.2 兔子问题
第一个月，有一对未成熟的兔子。第二个月，它们成熟。第三个月，它们能产下一对新的小兔子。所有兔子遵循相同规律，求第n个月的兔子数量。
分析：设第n个月兔子数为f(n)
- f(n) = 上个月兔子数 + 新生的小兔子数
- 新生的小兔子数 = 上个月成熟的兔子数
- 因为需要一个月兔子就成熟，所以【上个月成熟的兔子数】也就是【上上个月的兔子数】
- 上个月兔子数，即f(n - 1)；上上个月的兔子数，即f(n-2)
递推公式：f(n) = f(n -1) + f(n - 2)
class Solution {
public int f(int n) {
if(n == 1 || n == 2) {
return 1;
}
int a = 1; // f(n-2)
int b = 1; // f(n-1)
int count = 0;
for(int i = 3; i <= n; i++) {
count = a + b;
a = b; // 更新f(n-2)
b = count; // 更新f(n-1)
}
return count;
}
}3.3 汉诺塔问题（多路递归）
Tower of Hanoi，是一个源于印度古老传说：大梵天创建世界时做了三根金刚石柱，在一根柱子从下往上按大小顺序摞着 64 片黄金圆盘，大梵天命令婆罗门把圆盘重新摆放在另一根柱子上，并且规定
-
一次只能移动一个圆盘
-
小圆盘上不能放大圆盘
下面的动图演示了4片圆盘的移动方法
解法一：递归。时间复杂度：O(2^n)
递归分解：
- 若有n个盘子，以A、B和C分别表示起始柱、辅助柱和目标柱
- 首先，将前n-1个盘子从柱A移动到柱B，使用柱C作为辅助
- 接下来，将第n个盘子（最大的盘子）从柱A移动到柱C
- 最后，将n-1个盘子从柱B移动到柱C，使用柱A作为辅助
class Solution {
public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
int n = A.size();
moveDisks(n, A, C, B); // A -> C， B为辅助
}
private void moveDisks(int n, List<Integer> from, List<Integer> to, List<Integer> aux) {
// 基本情况：如果没有盘子要移动，直接返回
if (n == 0) {
return;
}
// 1. 将 n-1 个盘子从 "from" 移动到 "aux"，使用 "to" 作为辅助
moveDisks(n - 1, from, aux, to);
// 2. 将第 n 个盘子从 "from" 移动到 "to"
to.add(from.remove(from.size() - 1)); // 从 "from" 中移除最后一个盘子并添加到 "to"
// 3. 将 n-1 个盘子从 "aux" 移动到 "to"，使用 "from" 作为辅助
moveDisks(n - 1, aux, to, from);
}
} package com.itheima.algorithm.recursion_multi;
import org.springframework.util.StopWatch;
import java.util.LinkedList;
/**
* 递归汉诺塔
*/
public class E02HanoiTower {
static LinkedList<Integer> a = new LinkedList<>();
static LinkedList<Integer> b = new LinkedList<>();
static LinkedList<Integer> c = new LinkedList<>();
static void init(int n) {
for (int i = n; i >= 1; i--) {
a.addLast(i);
}
}
/**
* <h3>移动圆盘</h3>
*
* @param n 圆盘个数
* @param a 由
* @param b 借
* @param c 至
*/
static void move(int n, LinkedList<Integer> a,
LinkedList<Integer> b,
LinkedList<Integer> c) {
if (n == 0) {
return;
}
move(n - 1, a, c, b); // 把 n-1 个盘子由a,借c,移至b
c.addLast(a.removeLast()); // 把最后的盘子由 a 移至 c
// print();
move(n - 1, b, a, c); // 把 n-1 个盘子由b,借a,移至c
}
// T(n) = 2T(n-1) + c, O(2^64)
public static void main(String[] args) {
StopWatch sw = new StopWatch();
int n = 1;
init(n);
print();
sw.start("n=1");
move(n, a, b, c);
sw.stop();
print();
System.out.println(sw.prettyPrint());
}
private static void print() {
System.out.println("----------------");
System.out.println(a);
System.out.println(b);
System.out.println(c);
}
}
3.3 杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1 输出: [[1]]
提示:
1 <= numRows <= 30
递推公式：triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
解法一：迭代
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>(i + 1);
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
row.add(1); // 第一列和最后一列都为1
} else {
// 当前元素等于上一行的两个元素之和
row.add(triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j));
}
}
triangle.add(row); // 将当前行添加到三角形中
}
return triangle;
}
}解法二：递归。这个递归方法对于较大的 numRows（接近 30）可能会非常低效，因为会有大量重复计算。对于较大的输入，推荐使用迭代的方法。
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
for(int i = 0; i < numRows; i++) {
triangle.add(generateRow(i));
}
return triangle;
}
private List<Integer> generateRow(int rowIndex) {
List<Integer> row = new ArrayList<>();
for(int j = 0; j <= rowIndex; j++) {
row.add(getValue(rowIndex, j));
}
return row;
}
private int getValue(int row, int col) {
if(col == 0 || col == row) {
return 1;
}
return getValue(row - 1, col - 1) + getValue(row - 1, col);
}
}解法二：递归优化。备忘录模式
二维数组记忆法
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> triangle = new ArrayList<>();
// 创建一个二维数组用于存储已计算的值
Integer[][] memo = new Integer[numRows][numRows];
for (int i = 0; i < numRows; i++) {
triangle.add(new ArrayList<>());
for (int j = 0; j <= i; j++) {
triangle.get(i).add(getValue(i, j, memo));
}
}
return triangle;
}
private int getValue(int row, int col, Integer[][] memo) {
// 如果位置超出边界，返回 0
if (col < 0 || col > row) {
return 0;
}
// 如果是边界元素(最左或最右)，返回 1
if (col == 0 || col == row) {
return 1;
}
// 如果已经计算过，直接返回
if (memo[row][col] != null) {
return memo[row][col];
}
// 递归计算并存储结果到 memo
memo[row][col] = getValue(row - 1, col - 1, memo) + getValue(row - 1, col, memo);
return memo[row][col];
}
}解法三：一维数组记忆法。
private static void createRow(int[] row, int i) {
if (i == 0) {
row[0] = 1;
return;
}
for (int j = i; j > 0; j--) {
// 下一行当前项等于 上一行的当前项 + 前一项
row[j] = row[j] + row[j - 1];
}
}
public static void print2(int n) {
int[] row = new int[n];
for (int i = 0; i < n; i++) { // 行
createRow(row, i);
// printSpace(n, i);
for (int j = 0; j <= i; j++) {
System.out.printf("%-4d", row[j]);
}
System.out.println();
}
}4. 递归优化 - 记忆法
斐波那契数列计算过程中存在很多重复的计算，例如求f(5)的递归分解过程
可以看到（颜色相同的是重复的）
- f(3)重复了2次
- f(2)重复了3次
- f(1)重复了5次
- f(0)重复了3次
随着n的增大，重复次数非常可观，如何优化呢？
Menoization记忆法（也称备忘录）是一种优化技术，通过存储函数调用结果（通常比较昂贵），当再次出现相同的输入（子问题）时，就能实现加速效果。
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.618^n)；空间复杂度O(n)
- 改进后的时间复杂度为O(n)；空间复杂度为O(n)，额外的空间缓存结果
5. 递归优化 - 尾递归
用递归做 n + (n - 1) + (n - 2) + ... + 1
public static long sum(long n) {
if(n == 1) {
return 1;
}
return n + sum(n - 1);
}在我的机器上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)
...为什么呢？
- 每次方法调用都是需要消耗一定的栈内存的，这些内存用来存储方法参数、方法内局部变量、返回地址等。
- 方法调用占用的内存需要等待方法结束时才会释放
- 而递归调用不到最深不会回头，最内层方法没完成之前，外层方法都结束不了。
尾调用
如果函数的最后一步是调用一个函数，那么称为尾调用，例如
function a() {
return b()
}下面三段代码不能叫作尾调用
function a() {
const c = b()
return c
}- 最后一步并非调用函数
function a() {
return b() + 1
}- 最后一步执行的是加法
function a(x) {
return b() + x
}- 最后一步执行的是加法
一些语言的编译器能够对尾调用做优化，例如
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
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时出了异常
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)
...这时因为以上代码，这不是尾调用，要想成为尾调用，那么：
最后一行代码，必须是一次函数调用
内层函数必须摆脱与外层函数的关系，内层函数执行后不依赖于外层的变量或常量
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
执行流程如下，以伪码表示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);
}6. 递归时间复杂度 - 主定理（Master theorem）
若有递归式
其中
- T(n)是问题的运行时间，n是数据规模
- a是子问题的个数
- T(n/b)是子问题运行时间，每个子问题被拆成原问题数据规模的n/b
- f(n)是除递归外执行的计算
令x = log_b a，即x = log_子问题缩小倍数 子问题个数，那么
例1：T(n) = 2T(n/2) + n ^ 4
- 此时x = 1 < 4，由后者决定整个时间复杂度Θ(n^4)
例2：T(n) = T(7n / 10) + n
- 此时x = 0 < 1，由后者决定整个时间复杂度Θ(n)
例3：T(n) = 16T(n/4) + n^2
- a = 16, b = 4, x = 2, x = 2；此时x = c = 2，时间复杂度为Θ(n^2 * logn)
例4：T(n) = 7T(n/3) + n^2
- a = 7, b = 3, c = 2, x = 1.?；此时x < c，由后者决定整个时间复杂度Θ(n^2)
例5：T(n) = 7T(n/2) + n^2
- a = 7, b = 2, c = 2, x = 2.? > c，由前者决定整个时间复杂度Θ(n^log_2 7)
例6：T(n) = 2T(n/4) + sqrt(n)
- a = 2, b = 4, c = 1/2，x = c，时间复杂度为Θ(sqrt(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;
}
}- 子问题个数a = 1
- 子问题数据规模缩小倍数b = 2
- 除递归之外执行的计算是常数级c = 0
- 此时x = 0 = c，时间复杂度为Θ(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
- 子问题数据规模缩小倍数b = 2
- 除递归外，主要时间花在合并上，它可以用f(n) = n表示
- T(n) = 2T(n/2) + n，此时x = 1 = c，时间复杂度Θ(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
-
子问题数据规模缩小倍数
-
如果分区分的好，b=2
-
如果分区没分好，例如分区1 的数据是 0，分区 2 的数据是 n-1
-
-
除递归外，主要时间花在分区上，它可以用 $f(n) = n 表示
情况1 - 分区分的好
T(n) = 2T(n\2) + n
-
此时 x=1=c，时间复杂度 Θ(nlogn)
情况2 - 分区没分好
T(n) = T(n-1) + T(1) + n
-
此时不能用主定理求解
7. 递归时间复杂度 - 展开求解
像下面的递归式，都不能用主定理求解
例1：递归求和
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(n-(n-1)) + (n-1)c
-
其中 T(n-(n-1)) 即 T(1)
-
带入求得 T(n) = c + (n-1)c = nc
时间复杂度为 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(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)*(2+n)/2 = c + n^2/2 + n/2 -1
时间复杂度 O(n^2)
注：等差数列求和为 个数 * (首项 + 末项)/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 = n^2 / 2 + (2cn + n) / 2 -1
时间复杂度 O(n^2)
不会推导的同学可以进入 Wolfram|Alpha: Computational Intelligence
-
例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