算法

020 递归和master公式

递归需画图辅助理解，底层用系统栈实现。任何递归可转非递归，工程上常需避免栈溢出。Master公式适用于子问题规模相同的递归，根据log(b,a)与c关系判断复杂度。特例T(n) = 2*T(n/2) + O(n*logn)复杂度为O(n * (logn)^2)。

Posted by Hilda on March 15, 2025

1）从思想上理解递归：对于新手来说，递归去画调用图是非常重要的，有利于分析递归

2）从实际上理解递归：递归不是玄学，底层是利用系统栈来实现的

3）任何递归函数都一定可以改成非递归，不用系统帮你压栈（系统栈空间），自己压栈呗（内存空间）

4）递归改成非递归的必要性：

​ a. 工程上几乎一定要改，除非确定数据量再大递归也一定不深，归并排序、快速排序、线段树、很多的平衡树等，后面都讲

​ b. 算法笔试或者比赛中（能通过就不改）

5）master公式

​ a. 所有子问题规模相同的递归才能用master公式，T(n) = a * T(n/b) + O(n^c)，a、b、c都是常数

​ b. 如果log(b,a) < c，复杂度为：O(n^c)

​ c. 如果log(b,a) > c，复杂度为：O(n^log(b,a))

​ d. 如果log(b,a) == c，复杂度为：O(n^c * logn)

6）一个补充

` T(n) = 2T(n/2) + O(nlogn)，时间复杂度是O(n * ((logn)的平方))`，证明过程比较复杂，记住即可

1 从思想上理解递归：二分递归找最大值与递归决策图

如果是找数组最大值，可以通过下面的方法来完成（非递归）：

1
2
3
4
5
6
7
8

public int finMax(int[] nums) {
    if (nums.length == 0) return Integer.MIN_VALUE;
    int ans = nums[0];
    for (int n : nums) {
        if (ans < n) ans = n;
    }
    return ans;
}

如果要变成递归的写法呢？

1
2
3
4
5
6
7
8
9
10
11
12

public int findMaxRecursion(int[] nums) {
    if (nums.length == 0) return Integer.MIN_VALUE;
    return f(nums, 0, nums.length - 1);
}

public int f(int[] nums, int start, int end) {
    if (start == end) return nums[start];
    int m = start + ((end - start) >> 1);
    int lmax = f(nums, start, m);
    int rmax = f(nums, m + 1, end);
    return Math.max(lmax, rmax);
}

例如对于下面这个例子：

1

int[] arr = {1, 8, 3, 5, 9, 10, -1};

可以画递归决策图如下：

image-20250315142149184

其实“递归决策图”并不是一个专业的术语（或者说没有这个术语）。一般来说，递归决策图可以理解为一种通过递归方法构建或表示决策过程的图结构。

2 从实际上理解递归

许多理解不了的例子，建议画递归决策图。不用画栈的变化图。

对于上面这个例子：int[] arr = {1, 8, 3, 5, 9, 10, -1};，可以将栈变化过程绘制如下：

  1. f(0, 6)压栈
  • start = 0, end = 6，m = 3，调用f(0, 3)。
  • 栈状态（初始lmax和rmax未赋值）：
1
2
3
4
5
6
7

+------------------------+
| f(0, 6)                | <-- 栈顶
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(0, 3)压栈
  • start = 0, end = 3，m = 1，调用f(0, 1)。
  • 栈状态：
1
2
3
4
5
6
7
8
9
10
11

+------------------------+
| f(0, 3)                | <-- 栈顶
| m = 1, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(0, 1)压栈
  • start = 0, end = 1，m = 0，调用f(0, 0)。
  • 栈状态：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

+------------------------+
| f(0, 1)                | <-- 栈顶
| m = 0, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 3)                |
| m = 1, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(0, 0)压栈并弹出
  • start = 0, end = 0，基本情况，返回nums[0] = 1。
  • 压栈瞬间（无中间变量，因为是基本情况）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

+------------------------+
| f(0, 0)                | <-- 栈顶
| 返回 1                |
+------------------------+
| f(0, 1)                |
| m = 0, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 3)                |
| m = 1, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  • 弹出后，f(0, 1)的lmax = 1，调用f(1, 1)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

+------------------------+
| f(0, 1)                | <-- 栈顶
| m = 0, lmax = 1,      |
| rmax = ?              |
+------------------------+
| f(0, 3)                |
| m = 1, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(1, 1)压栈并弹出
  • start = 1, end = 1，返回nums[1] = 8。
  • 压栈瞬间：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

+------------------------+
| f(1, 1)                | <-- 栈顶
| 返回 8                |
+------------------------+
| f(0, 1)                |
| m = 0, lmax = 1,      |
| rmax = ?              |
+------------------------+
| f(0, 3)                |
| m = 1, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  • 弹出后，f(0, 1)的rmax = 8，计算max(1, 8) = 8，弹出：
1
2
3
4
5
6
7
8
9
10
11

+------------------------+
| f(0, 3)                | <-- 栈顶
| m = 1, lmax = 8,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+

然后左子树回溯并进入右子树

  1. f(0, 3)处理右子树
  • lmax = 8，调用f(2, 3)。
  • 栈状态：
1
2
3
4
5
6
7
8
9
10
11

+------------------------+
| f(0, 3)                | <-- 栈顶
| m = 1, lmax = 8,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(2, 3)压栈
  • start = 2, end = 3，m = 2，调用f(2, 2)。
  • 栈状态：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

+------------------------+
| f(2, 3)                | <-- 栈顶
| m = 2, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 3)                |
| m = 1, lmax = 8,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(2, 2)压栈并弹出
  • 返回nums[2] = 3。
  • 压栈瞬间：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

+------------------------+
| f(2, 2)                | <-- 栈顶
| 返回 3                |
+------------------------+
| f(2, 3)                |
| m = 2, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 3)                |
| m = 1, lmax = 8,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  • 弹出后：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

+------------------------+
| f(2, 3)                | <-- 栈顶
| m = 2, lmax = 3,      |
| rmax = ?              |
+------------------------+
| f(0, 3)                |
| m = 1, lmax = 8,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(3, 3)压栈并弹出
  • 返回nums[3] = 5。
  • 压栈瞬间：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

+------------------------+
| f(3, 3)                | <-- 栈顶
| 返回 5                |
+------------------------+
| f(2, 3)                |
| m = 2, lmax = 3,      |
| rmax = ?              |
+------------------------+
| f(0, 3)                |
| m = 1, lmax = 8,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  • 弹出后，f(2, 3)的rmax = 5，计算max(3, 5) = 5，弹出：
1
2
3
4
5
6
7
8
9
10
11

+------------------------+
| f(0, 3)                | <-- 栈顶
| m = 1, lmax = 8,      |
| rmax = 5              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = ?,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+

10.f(0, 3)回溯

  • 计算max(8, 5) = 8，弹出。
  • 栈状态：
1
2
3
4
5
6
7

+------------------------+
| f(0, 6)                | <-- 栈顶
| m = 3, lmax = 8,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(4, 6)压栈
  • start = 4, end = 6，m = 5，调用f(4, 5)。
  • 栈状态：
1
2
3
4
5
6
7
8
9
10
11

+------------------------+
| f(4, 6)                | <-- 栈顶
| m = 5, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = 8,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(4, 5)压栈
  • start = 4, end = 5，m = 4，调用f(4, 4)。
  • 栈状态：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

+------------------------+
| f(4, 5)                | <-- 栈顶
| m = 4, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(4, 6)                |
| m = 5, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = 8,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(4, 4)压栈并弹出
  • 返回nums[4] = 9。
  • 压栈瞬间：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

+------------------------+
| f(4, 4)                | <-- 栈顶
| 返回 9                |
+------------------------+
| f(4, 5)                |
| m = 4, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(4, 6)                |
| m = 5, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = 8,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  • 弹出后：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

+------------------------+
| f(4, 5)                | <-- 栈顶
| m = 4, lmax = 9,      |
| rmax = ?              |
+------------------------+
| f(4, 6)                |
| m = 5, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = 8,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(5, 5)压栈并弹出
  • 返回nums[5] = 10。
  • 压栈瞬间：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

+------------------------+
| f(5, 5)                | <-- 栈顶
| 返回 10               |
+------------------------+
| f(4, 5)                |
| m = 4, lmax = 9,      |
| rmax = ?              |
+------------------------+
| f(4, 6)                |
| m = 5, lmax = ?,      |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = 8,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  • 弹出后，f(4, 5)的rmax = 10，计算max(9, 10) = 10，弹出：
1
2
3
4
5
6
7
8
9
10
11

+------------------------+
| f(4, 6)                | <-- 栈顶
| m = 5, lmax = 10,     |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = 8,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  1. f(6, 6)压栈并弹出
  • 返回nums[6] = -1。
  • 压栈瞬间：
1
2
3
4
5
6
7
8
9
10
11
12
13
14

+------------------------+
| f(6, 6)                | <-- 栈顶
| 返回 -1               |
+------------------------+
| f(4, 6)                |
| m = 5, lmax = 10,     |
| rmax = ?              |
+------------------------+
| f(0, 6)                |
| m = 3, lmax = 8,      |
| rmax = ?              |
+------------------------+
| 空                    | <-- 栈底
+------------------------+
  • 弹出后，f(4, 6)的rmax = -1，计算max(10, -1) = 10，弹出：
1
2
3
4
5
6
7

+------------------------+
| f(0, 6)                | <-- 栈顶
| m = 3, lmax = 8,      |
| rmax = 10             |
+------------------------+
| 空                    | <-- 栈底
+------------------------+

16.f(0, 6)回溯

  • 计算max(8, 10) = 10，弹出。
  • 栈状态：
1
2
3

+------------------------+
| 空                    | <-- 栈底
+------------------------+

3 任何递归函数都一定可以改成非递归

首先明确：递归调用使用系统栈（Call Stack），非递归使用内存中的栈（用户自定义栈）

3.1 递归调用使用系统栈（Call Stack）

递归是通过函数调用自身实现的，每次调用都会在系统调用栈（由操作系统和编程语言运行时管理的内存区域）上分配一个新的栈帧（stack frame）。栈帧包含函数参数、局部变量和返回地址等信息。

代码中，f(nums, start, end)递归调用时，系统栈会逐层压入栈帧，直到基本情况触发后逐层弹出。

系统栈通常位于程序的栈区（stack segment），大小有限，由操作系统分配（例如Linux默认8MB，Windows默认1MB，可调整）。

递归实现逻辑清晰，符合分治法的数学模型，易于理解和维护.

对于天然具有递归结构的问题（如树、图、分治算法），递归代码更自然。

系统栈大小有限（通常几MB），当递归深度过大（例如数组长度为10^6）时，可能导致StackOverflowError。

栈大小由系统决定，调整需要修改运行时参数（例如Java的-Xss），不够灵活。

3.2 非递归使用内存中的栈（用户自定义栈）

非递归实现通常通过显式使用数据结构（如java.util.Stack或数组）模拟递归过程。这种栈是由程序员在代码中手动管理的，通常分配在堆内存（heap）中。

例如：可以用一个栈保存(start, end)对，循环处理直到栈为空，模拟递归的分治逻辑。

用户自定义栈在堆上分配，大小可以动态调整，受可用堆内存限制（通常远大于系统栈）。

上面的代码改成非递归就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public int findMaxNonRecursive(int[] nums) {
    if (nums.length == 0) return Integer.MIN_VALUE;
    
    // 定义一个栈保存 (start, end) 对
    Stack<int[]> stack = new Stack<>();
    stack.push(new int[]{0, nums.length - 1});
    int max = Integer.MIN_VALUE;
    
    while (!stack.isEmpty()) {
        int[] range = stack.pop();
        int start = range[0];
        int end = range[1];
        
        if (start == end) {
            max = Math.max(max, nums[start]);
        } else {
            int m = start + ((end - start) >> 1);
            // 先压右子树，再压左子树（模拟递归顺序）
            stack.push(new int[]{m + 1, end});
            stack.push(new int[]{start, m});
        }
    }
    return max;
}

自定义栈在堆内存中分配，受JVM堆大小限制（通常GB级别），可以处理更大的问题规模。

栈大小可动态调整（例如使用ArrayList或扩容数组），程序员可以根据需求优化内存使用。

避免了函数调用的开销（如栈帧分配和返回地址保存），在某些场景下更快。

需要手动管理栈，逻辑不如递归直观，增加了开发和维护成本。例如，非递归版本需要显式压栈和弹栈。

堆内存分配和垃圾回收（GC）可能引入额外开销，尤其是在频繁创建对象时。

栈的状态需要手动跟踪，调试时不如递归的调用栈清晰。

3.3 哪个更好？

小规模问题（深度浅）：递归更好。例如，数组长度小于1000，递归深度远低于系统栈限制，代码简洁性是主要优势。

大规模问题（深度大）：非递归更好。例如，数组长度为10^6，递归可能溢出，而自定义栈可以轻松应对。

4 递归改成非递归的必要性：

​ a. 工程上几乎一定要改，除非确定数据量再大递归也一定不深，例如（不改的如下）归并排序、快速排序、线段树、很多的平衡树等，后面都讲

​ b. 算法笔试或者比赛中（能通过就不改）

（1）如果能证明递归深度在任何输入下都不会超过系统栈限制，保留递归是可接受的。

  • 归并排序：
    • 递归深度：O(log n)，因为每次将数组分成两半。
    • 例如n = 10^6，深度约20，远低于栈限制，通常无需改。
  • 快速排序：
    • 平均递归深度：O(log n)，但最坏情况（已排序数组且选第一个元素为主元）为O(n)。
    • n = 10^6时最坏深度为10^6，需改成非递归或优化主元选择。
  • 线段树：
    • 构建和查询的递归深度：O(log n)，例如n = 10^6时约20。
    • 通常无需改，除非栈帧特别大（如包含复杂对象）。
  • 平衡树（如AVL、红黑树）：
    • 操作（如插入、删除）的递归深度：O(log n)，因为树高受平衡约束。
    • n = 10^6时约20，安全无需改。

结论：工程上，除非递归深度被严格限制在O(log n)或更低（且栈帧开销可控），否则应改成非递归以确保稳定性和性能。

b. 算法笔试或比赛中（能通过就不改）

在算法竞赛（如LeetCode、ACM、Codeforces）中，递归和非递归的选择更多是实用主义的，主要取决于以下因素：

5 master公式

回顾刚才的递归版本代码（找数组最大值的分治法），利用Master公式（主定理）分析其时间复杂度。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

public int findMaxRecursion(int[] nums) {
    if (nums.length == 0) return Integer.MIN_VALUE;
    return f(nums, 0, nums.length - 1);
}

public int f(int[] nums, int start, int end) {
    if (start == end) return nums[start]; // 基本情况
    int m = start + ((end - start) >> 1); // 中间点
    int lmax = f(nums, start, m);         // 左半部分递归
    int rmax = f(nums, m + 1, end);       // 右半部分递归
    return Math.max(lmax, rmax);          // 合并结果
}

递归逻辑：将问题分成两半，递归求解左右子问题，最后合并。

5.1 Master公式简介

Master公式用于分析分治递归的时间复杂度，形式为：\(T(n) = a * T(n/b) + O(n^c)\)

  • a：每次递归调用的子问题数量。
  • b：每个子问题的规模相对于原问题是1/b（即原问题规模缩小到n/b）。
  • c：合并子问题结果的复杂度（非递归部分）。

条件：所有子问题规模必须相同（或近似相同）。——-一定要注意这个条件

根据log(b, a)与c的关系，复杂度分为三种情况：

  1. 若\(log(b, a) < c\)，则\(T(n) = O(n^c)\)。
  2. 若\(log(b, a) > c\)，则\(T(n) = O(n^{log(b, a)})\)。
  3. 若\(log(b, a) == c，则T(n) = O(n^c * log n)\)。

5.2 应用Master公式分析

【分析一：】

分析f(nums, start, end)的时间复杂度，其中n = end - start + 1是当前子问题的规模。

a = 2：有两个子问题（左和右）。

b = 2：每个子问题规模为原问题的1/2。(一定要子问题规模相同才可以用master公式估计时间复杂度)

c = 0：合并部分Math.max(lmax, rmax)是O(1)，即O(\(n^0\))。

所以：\(log(b, a) = log(2, 2) = 1\)

比较log(b, a)与c：因为\(c = 0\)，所以\(log(b, a) > c\)

根据Master公式：若\(log(b, a) > c\)，则\(T(n) = O(n^{log(b, a)})\)。

所以时间复杂度是\(O(N)\)

这个递归版本的找数组最大值和遍历一遍数组找最大值，时间复杂度是一样的。

【分析二：】

有下面这样的递归代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

    public int findMaxModified(int[] nums) {
        if (nums.length == 0) return Integer.MIN_VALUE;
        return f(nums, 0, nums.length - 1);
    }

    public int f(int[] nums, int start, int end) {
        if (start == end) return nums[start]; // 基本情况

        int n = end - start + 1; // 当前区间长度
        int subSize = (2 * n) / 3; // 每个子问题规模为 2/3 n

        // 计算两个子问题的边界
        int m1 = start + subSize - 1; // 第一个子问题终点
        int m2 = end - subSize + 1;   // 第二个子问题起点

        // 边界检查
        if (m1 >= end) m1 = end;
        if (m2 <= start) m2 = start;

        // 两个子问题递归调用
        int lmax = f(nums, start, m1);    // 子问题 1: [start, m1]
        int rmax = f(nums, m2, end);      // 子问题 2: [m2, end]

        // 合并：扫描整个区间找最大值，O(n)
        int max = Integer.MIN_VALUE;
        for (int i = start; i <= end; i++) {
            max = Math.max(max, nums[i]);
        }
        return max;
    }

现在子问题规模变成了\(\frac{2}{3}N\)，并且子问题的调用次数是2次（虽然这么做没有什么意义，但是便于理解master 公式）

此时\(T(N) = T(\frac{2}{3}N)+T(\frac{2}{3}N) + O(1)\)

即\(T(N) = 2*T(\frac{2}{3}N)+O(1)\)，对照master公式的标准形式，就是\(a = 2, b = 3/2,c = 0\)

注意，此时b = 3/2，而不是2/3

下面估计时间复杂度：\(log(b, a) = log(3/2, 2) = log 2 / log (3/2)>1,c = 1\)，

那么时间复杂度就是\(O(n^{log(3/2, 2)}) ≈ O(n^{1.709})\)

【分析三：】

1
2
3
4
5
6
7
8
9
10
11

public static int f_printAll(int[] arr, int l, int r) {
    if (l == r) return arr[l];
    int m = l + ((r - l) >> 1);
    int maxLeft = f(arr, 0, m);
    int maxRight = f(arr, m + 1, r);

    for(int i = 0;i < arr.length;i++){
        System.out.println(i);
    }
    return Math.max(maxLeft, maxRight);
}

显然，此时a = 2, b = 2(子问题规模是N/2)，c = 1（此时由于打印整个数组，合并复杂度：O(N)，注意这里是常数N，与子问题规模n无关）

所以\(log(b, a) =1,c=1\)，即\(log(b, a)==c\)，则\(T(n) = O(n^c * log n)\)，时间复杂度就是\(O(N*logN)\)

5.3 master公式什么时候不能用？

如果递归中的子问题规模不是均匀的（即不是所有子问题都是n/b），Master公式不适用。

例如：

1
2
3
4

int f(int n) {
    if (n <= 1) return n;
    return f(n-1) + f(n-2); // 类似斐波那契数列
}

如果a或b随输入规模n变化，Master公式无法直接应用。

例如：

1
2
3
4
5
6
7
8

int f(int n) {
    if (n <= 1) return 1;
    int sum = 0;
    for (int i = 1; i <= n; i++) { // 子问题数量为 n
        sum += f(n/2);
    }
    return sum;
}

6 一个补充

` T(n) = 2T(n/2) + O(nlogn)`，(此时用不了master公式了)

由于上面这个情况比较常见，那么可以记住结论。

时间复杂度是\(O(n * ((logn)^2))\)，证明过程比较复杂，记住即可。

CATALOG
    FEATURED TAGS
    书籍阅读 算法 人工智能AI基础 机器学习-吴恩达 力扣 Java基础 numpy ollama工具 pandas
    FRIENDS