算法基础

基础数据结构

在学习算法前，一般应当掌握基础的数据结构。

Arrays

数组（Array） 是最基本的线性数据结构，它在内存中占据一段连续的存储空间，用于存储相同类型的元素。

数组的核心特性：

• 固定大小：数组在创建时需要指定长度，之后大小不可变（动态数组如Python的list底层会自动扩容，但本质上是创建新数组并复制）。
• 随机访问（Random Access）：通过下标可以在 \(O(1)\) 时间内直接访问任意位置的元素，因为地址可以通过 base_address + index * element_size 直接计算得出。
• 连续内存：元素在内存中紧密排列，具有良好的缓存局部性（Cache Locality），遍历效率高。

操作	时间复杂度	说明
访问（Access）	\(O(1)\)	通过下标直接访问
搜索（Search）	\(O(n)\)	无序数组需要线性扫描
插入（Insert）	\(O(n)\)	需要移动后续元素
删除（Delete）	\(O(n)\)	需要移动后续元素
尾部追加（Append）	\(O(1)\) 均摊	动态数组的均摊复杂度

在Python中，list就是动态数组的实现：

arr = [1, 2, 3, 4, 5]
print(arr[2])       # O(1) 随机访问，输出 3
arr.append(6)       # O(1) 均摊，尾部追加
arr.insert(0, 0)    # O(n)，头部插入需要移动所有元素

Matrix

矩阵（Matrix） 本质上是一个二维数组，用于存储 \(m \times n\) 的网格状数据。在算法题中，矩阵通常用来表示图的邻接关系、图像像素、动态规划的状态表等。

# 创建 m x n 的矩阵（初始化为0）
m, n = 3, 4
matrix = [[0] * n for _ in range(m)]

# 访问元素：matrix[row][col]，O(1)
matrix[1][2] = 5

矩阵的常见操作与复杂度：

操作	时间复杂度	说明
访问元素	\(O(1)\)	通过行列下标直接访问
遍历整个矩阵	\(O(m \times n)\)	需要访问每个元素
矩阵转置	\(O(m \times n)\)	行列互换
矩阵乘法（朴素）	\(O(n^3)\)	两个 \(n \times n\) 矩阵相乘

矩阵常见的遍历技巧包括：螺旋遍历、对角线遍历、层序遍历（BFS）等。在处理矩阵问题时，常需要注意边界条件和方向数组的使用：

# 四方向移动的方向数组
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

for dx, dy in directions:
    nx, ny = x + dx, y + dy
    if 0 <= nx < m and 0 <= ny < n:
        # 处理相邻格子
        pass

Stack

栈是一种遵循后进先出（LIFO: Last In, First Out） 原则的抽象数据类型。你可以把它想象成一叠盘子：你只能在最上面放盘子，也只能从最上面取盘子。最后放进去的盘子，最先被拿出来。

栈的核心操作包括：

• 入栈（Push） ：将一个新元素添加到栈的 顶部 。
• 出栈（Pop） ：从栈的顶部移除元素，并返回该元素的值。
• 栈顶元素（Peek/Top） ：返回栈顶元素的值，但不移除它。
• 判空（isEmpty） ：检查栈是否为空。

单调栈

单调栈是一种特殊的栈，它在整个操作过程中始终保持栈内元素的 单调性 ，即栈内元素是严格递增或严格递减的。当一个新元素 \(X\) 尝试入栈时，如果它破坏了栈原有的单调性，那么在 \(X\) 入栈之前，需要将栈顶所有不符合单调性要求的元素全部 弹出（Pop） ，直到栈重新满足单调性要求，或栈为空。然后，新元素 \(X\) 才能入栈。

单调栈常用来解决下列问题：

• 找到下一个更大的元素
• 最大矩形面积

Queue

队列（Queue）是一种遵循先进先出（FIFO: First In, First Out） 原则的抽象数据类型。你可以把它想象成排队买票：第一个排队的人，第一个买到票离开。

队列的核心操作包括：

• 入队（Enqueue/Push） ：将一个新元素添加到队列的 尾部（Rear） 。
• 出队（Dequeue/Pop） ：从队列的头部（Front） 移除元素。
• 队头元素（Peek/Front） ：返回队头元素的值，但不移除它。
• 判空（isEmpty） ：检查队列是否为空。

队列在计算机科学中有广泛的应用，例如：

• 任务调度 ：在操作系统和服务器中，用来管理等待执行的任务或请求。
• 广度优先搜索（BFS） ：在图和树的遍历中，用于按层级访问节点。
• 打印任务管理 ：打印机通常使用队列来处理待打印的文档。

Deque

双端队列 (Deque)允许在队列两端（即头部和尾部）进行入队和出队操作。

单调队列

单调队列（Monotonic Queue）通常是基于Deque实现的。单调队列利用双端队列的特性来维护队列的单调性，其主要目的是 在一个滑动窗口内，快速求出最大值或最小值 。

• 维护单调性 ：当一个新元素 \(X\) 从尾部尝试入队时，如果它破坏了队列原有的单调性，需要将尾部所有不符合单调性要求的元素全部 弹出 。
  • 例如，维护 递减队列 （队头是最大值）：新元素 \(X\) 入队前，如果队尾元素 \(Y < X\)，则 \(Y\) 出队。这样可以确保队内元素总是递减的。
• 处理窗口滑动 ：当滑动窗口向右移动时，需要检查队头元素是否已经滑出窗口范围。如果队头元素的位置索引小于或等于当前窗口的起始索引，则需要将队头元素 出队 。
• 获取最值 ：由于队列是单调的，所以队头元素始终是当前窗口内的 最大值 （对于递减队列）或 最小值 （对于递增队列）。

常见应用包括：

• 滑动窗口最大值/最小值
• 动态规划优化

Linked List

链表（Linked List） 是一种动态的线性数据结构，与数组不同，链表中的元素在内存中不需要连续存储。每个元素称为节点（Node），节点通过指针（Pointer） 连接到下一个节点，形成链式结构。

单链表（Singly Linked List） 的节点包含两个部分：数据域（data） 和指向下一个节点的指针域（next）。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

链表的核心操作与复杂度：

操作	时间复杂度	说明
访问第 \(k\) 个元素	\(O(n)\)	必须从头节点开始逐个遍历
头部插入/删除	\(O(1)\)	只需修改头指针
尾部插入	\(O(n)\)	需要遍历到尾部（无尾指针时）
在给定节点后插入/删除	\(O(1)\)	只需修改指针
搜索	\(O(n)\)	需要线性遍历

链表与数组的核心区别在于：数组的优势是随机访问 \(O(1)\)，而链表的优势是插入删除 \(O(1)\)（已知位置时）。链表不需要预先分配空间，适合频繁增删的场景。

哨兵节点（Dummy Node） 是链表题中常用的技巧。在链表头部添加一个虚拟节点，可以统一处理头节点的插入和删除操作，避免大量的边界判断：

def delete_node(head, target):
    dummy = ListNode(0, head)  # 哨兵节点
    prev = dummy
    curr = head
    while curr:
        if curr.val == target:
            prev.next = curr.next  # 删除当前节点
        else:
            prev = curr
        curr = curr.next
    return dummy.next  # 返回真正的头节点

Doubly Linked List

双向链表（Doubly Linked List） 的每个节点除了存储数据和指向下一个节点的指针外，还存储一个指向前一个节点的指针（prev）。

class DoublyListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

相比单链表，双向链表的优势在于：

• 双向遍历：可以从任意节点向前或向后遍历，而单链表只能向后遍历。
• 删除当前节点为 \(O(1)\)：在单链表中，删除一个节点需要知道其前驱节点（需要 \(O(n)\) 遍历找到）；而在双向链表中，可以直接通过 prev 指针找到前驱节点。
• LRU Cache 的核心数据结构：双向链表配合哈希表，可以实现 \(O(1)\) 时间复杂度的 LRU（Least Recently Used）缓存淘汰算法。

双向链表的缺点是每个节点需要额外存储一个 prev 指针，空间开销更大。

其他数据结构

以下数据结构参见Tree算法笔记：

• Tree
• BST
• Heap
• 斐波那契堆

以下数据结构参见Graph算法笔记：

• Graph
• Union-Find (DSU)

以下数据结构参加String算法笔记：

• String
• Trie

算法分析

算法分析框架

一般来说，一个完整的算法一般包含如下内容：

• Description
• Pseudocode
• Actual Code
• Justification
• Time Analysis
• Space Analysis

Description就是描述算法内容，Justification就是合理性证明或论证，用来说明算法分析结果的正确性。

比如说，对于算法中的循环，我们需要证明迭代算法的正确性。循环不变量（Loop Invariant） 就是用来论争算法在执行过程中没有丢失或损坏关键属性的。

循环不变量的证明包含下面三个内容：

• 初始化（Initialization），证明不变量在第一次迭代开始时是成立的
• 保持（Maintanance），证明如果假设不变量在某次迭代开始时是成立的，那么在这次迭代 结束之后 ，它对下一次迭代的开始依然成立。
• 终止（Termination），证明当循环结束时，不变量提供了一个有用的陈述，该陈述证明了算法的最终目标已经达成。

除了循环不变量，时间复杂度、空间复杂度等一般也要Justification。

算法分析的数学基础

本节整理了一些本书中经常涉及到的一些数学相关的知识，基本都是比较基础的数学内容。

0.1 指数增长快于多项式函数

在算法分析中有一个至关重要的规律：任何指数函数的增长速度都比任何多项式函数快。

• 多项式函数 (Polynomials) ：形如\(n^b\)的函数，其中 b 是一个常数。例如：\(n^2\), \(n^{100}\)都是多项式。
• 指数函数 (Exponentials) ：形如\(a^n\)的函数，其中 a 是一个大于 1 的常数。例如：\(2^n\), \(1.1^n\)都是指数函数。

对于多项式函数和指数函数，如果a > 1，那么我们有：

\[ \lim_{n \to \infty} \frac{n^b}{a^n} = 0 \]

这个极限公式表明当n趋向于无穷大时，一个多项式函数和一个指数函数的比值会趋近于0。这意味着分母的增长速度远快于分子的增长速度，因此在极限情况下他们的比值几乎为0。

通过这个我们可以得到如下推论：

\[ n^b = O\!\left(a^n\right) \]

即指数函数一定是多项式函数的上限。（在a>1的情况下）

---

0.2 Notation

• \(\log_b n = a \iff b^a = n\) (definition of log)
• \(\ln n = \log_e n\) (natural log)
• \(\lg n \ \text{or} \ \log n = \log_2 n\) (base-2 shorthand)
• \(\lg^2 n = (\lg n)(\lg n)\) (multiplication)
• \(\lg \lg n = (\lg(\lg n))\) (composition)

---

0.3 Notation Properties

• \((a^m)^n = a^{mn}\)
• \(a^m \cdot a^n = a^{m+n}\)
• \(a^n = 2^{n \lg a}\)
• \(a^{\log_b n} = n^{\log_b a}\)
• \(\log_b a = \dfrac{\log_c a}{\log_c b}\) (A way to change from base \(b\) to base \(c\))
• \(\lg ab = \lg a + \lg b\)
• \(\lg(a^x) = x \lg a\)
• \(\lg(1/a) = -\lg a\)

---

0.4 Quantifiers

Quantifiers就是量词，用来限定一个陈述在某个集合中是对全部成立，抑或是对至少有一个成立。

• Universal Quantifier (\(\forall\)): The symbol \(\forall\) is used to express that a statement holds for every element in a given set. For example:

  $$ \forall x \in \mathbb{R}, \; x^2 \geq 0 $$ - Existential Quantifier (\(\exists\)): The symbol \(\exists\) is used to express that there exists at least one element in a given set for which a statement holds. For example:

  \[ \exists x \in \mathbb{R} \;\; \text{such that} \;\; x^2 = 4 \]

简单来说：

• ∀ (任意)： 要求很高，必须对集合里所有成员都成立才算对。∀ 符号看起来像一个倒过来的字母 "A"，可以联想英文单词 "All" (所有)。
• ∃ (存在)： 要求很低，只需要在集合里找到至少一个符合条件的成员就算对。∃ 符号看起来像一个反过来的字母 "E"，可以联想英文单词 "Exists" (存在)。

这两个符号在定义数学概念（比如我们之前讨论的 Big O 定义）和进行逻辑证明时非常关键。

---

0.5 等差数列求和公式（Arithmetic series）

For integer \(n \geq 1\), we have

\[ 1 + 2 + \dots + n \;=\; \sum_{k=0}^n k \;=\; \frac{n(n+1)}{2} \]

---

0.6 等比数列求和公式（Geometric series）

For real \(r \neq 1\), we have

\[ 1 + r + r^2 + \dots + r^k \;=\; \sum_{i=0}^k r^i \;=\; \frac{1 - r^{k+1}}{1-r} \]

When the summation is infinite and \(|r| < 1\), we have

\[ 1 + r + r^2 + \dots \;=\; \sum_{i=0}^{\infty} r^i \;=\; \frac{1}{1-r} \]

---

0.7 离散数学和集合

Let \(A\) and \(B\) be sets.

Union并集，Intersection交集，Difference差集：

• Union: \(A \cup B =\) The set of elements that appear in either \(A\) or \(B\) or both.
• Intersection:\(A \cap B =\) The set of elements that appear in both \(A\) and \(B\).
• Difference:\(A \setminus B\) or \(A - B =\) The set of elements that appear in \(A\) and not in \(B\).

基数：（集合A中元素的个数）

• Cardinality:\(|A| =\) The number of elements in \(A\).

阶乘

• Factorial: The notation \(n!\) is read “\(n\) factorial” and is defined for integer \(n > 0\) as follows:

  \[ n! = 1 \times 2 \times \dots \times (n-1) \times n \]

  By convention, \(0! = 1\).

Choose选择，Permutations排列，Combinations组合：

• “Choose”: The notation \(\binom{n}{k}\) is read “\(n\) choose \(k\)” because it represents the number of ways to choose \(k\) items from \(n\) distinct items.For integers \(0 \leq k \leq n\), we have:

  $$ \binom{n}{k} = \frac{n!}{k!(n-k)!} = \binom{n}{n-k} $$ - Permutations and Combinations: In a set of elements \(A\), the number of ordered permutations of all \(|A|\) elements is \(|A|!\). The number of combinations of \(k\) elements is

  \[ \binom{|A|}{k}. \]

排列和组合的最重要区别就是：排列中顺序很重要，而组合中顺序不重要。比如ABC和CAB是两种不同的排列，但是却是2同一个组合。

---

0.8 Probability

• Random Variables: In probability theory, a random variable is a variable whose possible values are outcomes of a random phenomenon.For example, let \(X\) represent the outcome of rolling a six-sided die.\(X\) can take values \(\{1,2,3,4,5,6\}\).
• Notation:\(P(X = 5) = \tfrac{1}{6}\) means “The probability that \(X\) takes the value \(5\) is \(\tfrac{1}{6}\).”

Expectation 期望

• Expectation: The expectation (or mean) of a random variable \(X\) is denoted by \(E[X]\) and represents the average value it takes. For a discrete random variable, it is computed as:

  \[ E[X] = \sum_x x \cdot P(X = x) \]

  where the sum is taken over all possible values of \(X\).

Example: Consider a fair six-sided die. Let \(X\) be the outcome of a single roll. The expectation of \(X\) is:

\[ E[X] = \tfrac{1}{6}(1) + \tfrac{1}{6}(2) + \tfrac{1}{6}(3) + \tfrac{1}{6}(4) + \tfrac{1}{6}(5) + \tfrac{1}{6}(6) = \tfrac{7}{2} \]

Properties of Expectation:

• \(E[aX + b] = aE[X] + b\) for constants \(a\) and \(b\).
• \(E[X + Y] = E[X] + E[Y]\) for independent random variables \(X\) and \(Y\).

---

0.9 Ceilings and Floors

• \(\lceil x \rceil = \text{ceiling}(x) =\) the least integer greater than or equal to \(x\)
• \(\lfloor x \rfloor = \text{floor}(x) =\) the greatest integer less than or equal to \(x\)

复杂度分析

在算法分析中，我们采用Asymptotic Notation，也即渐进记法，来分析算法的效率。其包含三个核心概念：

• Big O
• Big Omega \(\Omega\)
• Big Theta \(\Theta\)

Big O

• Definition: The function \(f(n)\) is \(O(g(n))\) if there exist constants \(c > 0\) and \(n_0\) such that

  $$ 0 \leq f(n) \leq c \cdot g(n) \quad \text{for all } n \geq n_0. $$ - Example: \(2n^2 + 3n + 1\) is \(O(n^2)\) because for \(c = 3\) and \(n_0 = 1\), we have

  \[ 0 \leq 2n^2 + 3n + 1 \leq 2n^2 + 3n^2 + 1 \cdot n^2 \leq 6n^2 , \quad \text{for all } n \geq 1 \]

一般来说，Big O描述了一个函数增长速度的上限（Upper Bound）。可以这样理解：“当输入规模 n 足够大时，函数 f(n) 的增长速度不会超过函数 g(n) 的 c 倍。

通常n0选取为1，或者大于1的一个整数。（虽然在上述定义中没有说明n0必须大于等于1，但是一般在算法分析中我们默认n0是大于等于1的。因为我们在分析复杂性的时候，关心的是渐进性为，目的是描述函数的长期增长趋势，因此如果n0起始于负数，在这个应用中是没有意义的。）

也就是说，在算法分析中，g(n)是f(n)的太牛花瓣，并且我们不关注常数因子。所以当我们去分析一个算法的Big O的时候，我们只需要找到合适的c和n，找到g(n)就可以了。

从数学定义上来说，上面的例子就算给出 O(n³) ，仍然也是一个正确的上限，但它是一个很“松”的上限，没有精确地反映出函数 2n 的增长趋势。这就像问一个小孩多高，你说：“他肯定不超过3米高。” 这句话虽然没错，但没什么用。我们更想听到的是：“他大概1米2高。”所以，当我们分析算法复杂度时，虽然有无数个正确的 Big O 答案，但我们总是约定俗成地去寻找并给出一个最简单、最贴近的那个，也就是 最小的那个增长率 。如果能找到严格上界，有时候也会写作o记号（小o）。

在记录Big O的时候，一般有两种常见写法：

• f(n) = O(n²) ：这是最常见、最通用的写法。它读作 “f(n) is O of n-squared”（f(n) 是 n 平方的 Big O）。虽然这里用的是等号 =，但它并不表示数学上严格的“相等”，而是一种约定俗成的表示法，意思是“f(n) 的增长率属于 O(n²) 这个级别”。
• f(n) ∈ O(n²) ：这是从数学集合角度来看更严谨的写法。这里的 ∈ 符号表示“属于”（is an element of）。O(n²) 实际上代表一个 函数的集合 ，这个集合包含了所有增长速度不超过 n² 的函数。所以 f(n) ∈ O(n²) 的意思是 “f(n) 是 O(n²) 这个集合中的一员”。

---

※ 证明Big O性质

如果 f(n) = O(g(n)) 并且 h(n) = O(g(n))，那么 f(n) + h(n) = O(g(n))。

用通俗的语言解释就是： 如果两个函数 f(n) 和 h(n) 的增长率都最多和 g(n) 一样快（或者更慢），那么这两个函数的和 f(n) + h(n) 的增长率也最多和 g(n) 一样快。

这在算法分析中非常有用。比如，如果你有两个连续的代码块，它们的运行时间分别是 O(n) 和 O(n)，那么整个过程的运行时间就是 O(n) + O(n)，根据这个定理，结果依然是 O(n)。

PROOFS

证明过程是严格按照大O表示法的定义来进行的。我们一步一步来看：

1. 假设 (Suppose)

Suppose f = O(g) and h = O(g).

证明的第一步是假设论点的前提条件成立。这里我们假设 f 的增长率是 O(g)，h 的增长率也是 O(g)。 （图片右上角提示，f 是 f(n) 的简写，这在数学证明中很常见。）

2. 展开 f = O(g) 的定义

f = O(g) means f ≤ c*g for n ≥ n₀.

这是大O表示法的正式定义。f(n) = O(g(n)) 的意思是： 存在一个正常数 c 和一个整数 n₀，使得当 n 大于等于 n₀ 时，f(n) 的值总是不超过 c 乘以 g(n) 的值。

• c 是一个常量系数，它允许我们忽略常数倍的差异。
• n₀ 是一个阈值，它表示我们只关心当输入规模 n 足够大时的情况。

3. 展开 h = O(g) 的定义

h = O(g) means h ≤ d*g for n ≥ n₁.

同理，h(n) = O(g(n)) 的意思是： 存在另一个正常数 d 和另一个整数 n₁，使得当 n 大于等于 n₁ 时，h(n) 的值总是不超过 d 乘以 g(n) 的值。 注意： 这里的常数 d 和阈值 n₁ 可能与上面 f(n) 的 c 和 n₀ 不同。

4. 相加 (Adding gives)

Adding gives f + h ≤ (c+d)g for n ≥ ?

现在，为了证明 f(n) + h(n) 的情况，我们将上面两个不等式相加： f(n) ≤ c*g(n) h(n) ≤ d*g(n) 两式相加得到： f(n) + h(n) ≤ c*g(n) + d*g(n) 提取公因式 g(n)，得到： f(n) + h(n) ≤ (c+d)g(n)

5. 确定新的阈值 n（图片中未写完的部分） 关键问题来了：这个新的不等式 f+h ≤ (c+d)g 在什么条件下成立呢？

• 第一个不等式 f ≤ c*g 要求 n ≥ n₀。
• 第二个不等式 h ≤ d*g 要求 n ≥ n₁。 为了让两个不等式同时成立，n 必须同时满足 n ≥ n₀ 和 n ≥ n₁。因此，我们只需要取两者中较大的那个值作为新的阈值即可。 所以，我们定义一个新的阈值 n₂ = max(n₀, n₁)。当 n ≥ n₂ 时，上面两个不等式都成立，因此它们的和也成立。

所以，图片中那个空白的地方应该填 max(n₀, n₁)。

结论

我们已经证明了： 存在一个新的常数 C = c+d 和一个新的阈值 n₂ = max(n₀, n₁)，使得当 n ≥ n₂ 时，f(n) + h(n) ≤ C * g(n)。

这完全符合大O表示法的定义！因此，我们得出结论：f(n) + h(n) = O(g(n))。证明完毕。

简单例子

假设 f(n) = 2n + 10，h(n) = 3n + 5，我们要证明 f(n) + h(n) 是 O(n)。

1. 证明 f(n) = O(n) : 我们需要找到 c 和 n₀ 使得 2n + 10 ≤ c*n。 如果我们选 c = 3，那么 2n + 10 ≤ 3n -> 10 ≤ n。所以，当 c₁=3, n₀=10 时，f(n) = O(n) 成立。
2. 证明 h(n) = O(n) : 我们需要找到 d 和 n₁ 使得 3n + 5 ≤ d*n。 如果我们选 d = 4，那么 3n + 5 ≤ 4n -> 5 ≤ n。所以，当 c₂=4, n₁=5 时，h(n) = O(n) 成立。
3. 证明 f(n) + h(n) = O(n) : f(n) + h(n) = (2n+10) + (3n+5) = 5n + 15。 根据上面的证明，我们应该有 f(n) + h(n) ≤ (c₁+c₂)n 对于 n ≥ max(n₀, n₁) 成立。

• 新常数 C = c₁ + c₂ = 3 + 4 = 7。
• 新阈值 n₂ = max(n₀, n₁) = max(10, 5) = 10。
• 我们来验证一下：5n + 15 ≤ 7n 是否在 n ≥ 10 时成立？ 15 ≤ 2n -> 7.5 ≤ n。 因为 n ≥ 10 已经满足了 n ≥ 7.5 的条件，所以这个不等式是成立的。

因此，我们成功证明了 f(n) + h(n) = O(n)。

---

Big Omega

• Definition: The function \(f(n)\) is \(\Omega(g(n))\) if there exist constants \(c > 0\) and \(n_0\) such that

  $$ 0 \leq c \cdot g(n) \leq f(n) \quad \text{for all } n \geq n_0. $$ - Example: \(2n^2 + 3n + 1\) is \(\Omega(n^2)\) because for \(c = 2\) and \(n_0 = 1\), we have

  \[ 0 \leq 2n^2 \leq 2n^2 + 3n + 1, \quad \text{for all } n \geq 1 \]

一般来说，Big Omega描述了一个函数增长速度的下限（Lower Bound）。可以这样理解：“当输入规模 n 足够大时，函数 f(n) 的增长速度至少和函数 g(n) 的 d 倍一样快。” 也就是说，g(n) 是 f(n) 的一种“地板”，f(n) 的增长再慢也慢不过 g(n)。在算法分析中，它常用来描述一个算法的 最好情况下的时间复杂度 。

对于所有增长的函数 f(n)（比如算法的运行时间），我们几乎总可以说 f(n) = Ω(1)（因为运行时间至少是一个常数，不会是负数）。但是，这同样是一个没有信息量的“松”的下限。

我们使用 Big Omega 是想知道：“这个算法的运行时间最少也要增长得多快？” 说 Ω(1) 等于在说：“这个算法总得花点时间才能运行完。” 这是一句废话。说一个排序算法是 Ω(n) 意味着：“不管输入的数据有多好（比如已经排好序了），你至少也得把每个元素看一遍，所以时间下限是线性增长的。” 这个信息就非常有用了。

所以在实际分析中，和 Big O 一样，我们一半呢寻找的是最紧的下限（Tightest Lower Bound），也就是增长最快的那个下界函数，来提供有意义的分析。如果能找到严格下界，记录时也用小omega，也即\(\omega\)来表示。

---

Big Theta

• Definition: The function \(f(n)\) is \(\Theta(g(n))\) if it is both \(O(g(n))\) and \(\Omega(g(n))\).
• Example: \(2n^2 + 3n + 1\) is \(\Theta(n^2)\) because it is both \(O(n^2)\) and \(\Omega(n^2)\).

f(n) = Θ(g(n)) 的意思是：存在正常数 c, d 和 n₀，使得对于所有 n ≥ n₀，都有 d * g(n) ≤ f(n) ≤ c * g(n)。Big Theta 描述了一个函数增长速度的 紧密界限 (Tight Bound) 。它其实是 Big O 和 Big Omega 的结合。f(n) = Θ(g(n)) 意味着 f(n) 的增长速度既不比 g(n) 快，也不比 g(n) 慢，它们的增长速率是相同的。也就是说，f(n) 被 g(n) 从上下两个方向“夹住”了。这是对一个算法复杂度最精确的描述。

一般来说，如果我们在找Big O和Big Omega的时候，找到的如果已经是最紧的上限和最紧的下限，那么这个时候用这两个最紧的上下限就能轻松找到那个被夹住的紧密界限。

递归

递归

递归是一种解决问题的方法，在计算机科学中，我们在一个函数内部调用函数自身，就形成了递归。

比如说：

def factorial(n):
    # 递归终止条件（基例）
    if n == 1:
        return 1
    # 递归调用
    return n * factorial(n - 1)

print(factorial(5))  # 输出：120

其工作原理如下：

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * 4 * 3 * 2 * 1
= 120

在计算机内部，递归的实现依赖于 运行时栈（Runtime Stack） ，也称为 调用栈（Call Stack） 。每次函数调用（无论是调用其他函数还是调用自身）时，计算机都需要记录 当前函数的运行环境 ，以便函数执行完毕后能正确返回，这个机制就是通过栈来实现的。

既然内部是用栈实现的，那么我们当然也可以用一个显式的栈数据结构来实现。在计算机科学中，任何递归算法理论上都可以转换为等价的 迭代（Iterative）算法，而这个迭代算法的核心就是使用一个显式管理的栈结构 。

上面的斐波那契数列改为显示栈的版本如下：

def factorial_stack(n):
    stack = []      # 用来模拟递归调用栈
    result = 1

    # 模拟递归“向下调用”的过程
    while n > 1:
        stack.append(n)
        n -= 1

    # 模拟递归“向上返回”的过程
    while stack:
        result *= stack.pop()

    return result

print(factorial_stack(5))  # 输出：120

使用显式栈的好处是可用空间远大于系统调用栈，从而可以处理更深、更大规模的递归问题。此外，显式栈在性能上也更好，因此在后面学到DFS等递归算法时，基本都有对应的迭代版本，且在实际使用中非常常见。

这里要注意，从计算机执行和代码实现的角度来看，迭代实现不算递归，因为它没有用到函数调用栈；然而从算法设计思想和问题分解的角度来看，迭代实现仍然是递归思想的应用。

分治思想

分治是分而治之的意思。分治一定是递归，但递归不一定是分治。分治法（Divide and Conquer）的核心思想就是把一个大问题分解为若干个小问题（或者说子问题），然后递归求解，把子问题的解组合起来得到原问题的解 。

分治通常包含三个步骤 ：

1. Divide 分： 将原问题分解成 \(k\) 个规模较小的子问题。这些子问题通常是独立的，且与原问题 形式相同 。
2. Conquer 治： 如果子问题的规模足够小（达到 基础情况/Base Case ），则直接求解。否则，继续递归调用分治过程。
3. Combine 合： 将子问题的解组合起来，形成原问题的最终解。这个“合并”步骤是分治算法中往往最巧妙和关键的部分。

分治策略在许多高效的算法中得到了广泛应用，比如：

归并排序 (Merge Sort)

• 分 (Divide): 将待排序的数组分成左右两个子数组。
• 治 (Conquer): 递归地对这两个子数组进行排序。
• 合 (Combine): 将两个已排序的子数组合并成一个完整的有序数组。

快速排序 (Quick Sort)

• 分 (Divide): 选择一个 基准元素 (Pivot) ，通过一次扫描（分区操作）将数组分为两部分：小于 Pivot 的元素和大于 Pivot 的元素。
• 治 (Conquer): 递归地对这两部分进行排序。
• 合 (Combine): 由于分区操作已经将元素归位， 合并步骤非常简单 （只需按顺序连接两部分和 Pivot 即可，或者可以说合并成本几乎为零）。

二分查找 (Binary Search)

• 分 (Divide): 将查找区间分成两半。
• 治 (Conquer): 根据目标值与中间元素的大小关系，只在其中一半区间内递归查找。
• 合 (Combine): 查找成功则返回索引，查找失败则返回未找到的信号（ 没有实际的合并操作 ）。

Strassen 矩阵乘法

• 分 (Divide): 将 \(N \times N\) 矩阵分成四个 \((N/2) \times (N/2)\) 的子矩阵。
• 治 (Conquer): 递归地计算七次 \((N/2) \times (N/2)\) 矩阵乘法（而非传统方法的八次）。
• 合 (Combine): 通过对这七个结果进行加减运算，合成最终的 \(N \times N\) 矩阵乘积。

递归式

递归或分治算法的运行时间 \(T(n)\) 通常用递归式 (Recurrence Relation) 来描述和分析。对于一个典型的分治算法：

1. 分和合的成本： \(f(n)\)
2. 子问题数量 ： \(a\)
3. 子问题规模 ： \(n/b\)

运行时间的递归式通常写成以下形式：

\[ T(n) = aT(n/b) + f(n) \]

例如，归并排序的递归式为 \(T(n) = 2T(n/2) + O(n)\)，其中 \(a=2\) (两个子问题)，\(b=2\) (规模减半)，\(f(n)=O(n)\) (合并成本)。通过求解这个递归式，我们知道归并排序的时间复杂度为 \(O(n \log n)\)。

写出递归式的目的是分析时间复杂度，计算机科学家们已经总结出了一些非常好用的工具来快速求解递归式，最常用的方法包括：

• 主定理 Master Theorem
• 递归树法 Recursion-Tree Method
• 代入法 Substitution Method

主定理

主定理（Master Theorem）或主方法（Master Method）是一个用来快速求解特定形式的算法递归式，其标准形式如下：

\[ T(n) = aT\!\left(\tfrac{n}{b}\right) + f(n) \]

其中 \(a \ge 1\), \(b > 1\) 是常数， \(f(n)\) 是渐近正函数：

• \(a\): 子问题的数量
• \(n/b\): 每个子问题的规模（假设每个子问题规模相同）
• \(f(n)\): 分解问题和合并子问题解所花费的时间（非递归部分）

主方法的核心思想就是通过比较 \(f(n)\) 和 \(n^{\log_b a}\) 的渐近关系，给出 \(T(n)\) 的解：

关系	情况描述	结论
情况 1	\(f(n) = O(n^{\log_b a - \epsilon})\)(\(n^{\log_b a}\) 更大 ，大得多)	\(T(n) = \Theta(n^{\log_b a})\)
情况 2	\(f(n) = \Theta(n^{\log_b a})\)(\(n^{\log_b a}\) 相等 )	\(T(n) = \Theta(n^{\log_b a} \log n)\)
情况 3	\(f(n) = \Omega(n^{\log_b a + \epsilon})\)(\(n^{\log_b a}\) 更小 ，小得多)	\(T(n) = \Theta(f(n))\)

注意： \(\epsilon\) 是一个大于 0 的常数

---

举几个例子说明主方法如何使用：

a.

\[ T(n) = 2T\!\left(\tfrac{n}{4}\right) + 1 \]

1. 分析：

   • \(f(n) = 1\)
   • 比较 \(f(n) = 1\) 和 \(n^{\log_b a} = \sqrt{n}\)。
   • 很明显，\(f(n)\) 的增长速度远慢于 \(\sqrt{n}\)。严格来说，\(f(n) = 1 = O(n^{0.5 - \varepsilon})\)，例如我们可以取 \(\varepsilon = 0.5\)。
   • 这符合主方法的 情况一 (Case 1)。 2. 结论：
   • 总成本由 \(n^{\log_b a}\) 决定。
   • \[ T(n) = \Theta\!\bigl(n^{\log_b a}\bigr) = \Theta(\sqrt{n}) \]

---

b.

\[ T(n) = 2T\!\left(\tfrac{n}{4}\right) + \sqrt{n} \]

1. 分析：

   • \(f(n) = \sqrt{n}\)
   • 比较 \(f(n) = \sqrt{n}\) 和 \(n^{\log_b a} = \sqrt{n}\)。
   • 两者渐近相等。严格来说，\(f(n) = \Theta\!\bigl(n^{1/2}\log^0 n\bigr)\)，即 \(k = 0\)。
   • 这符合主方法的 情况二 (Case 2)。 2. 结论：
   • 总成本需要在原有基础上追加一个对数因子。
   • \[ T(n) = \Theta\!\bigl(n^{\log_b a}\log^{k+1} n\bigr) = \Theta\!\bigl(\sqrt{n}\log^{0+1} n\bigr) = \Theta\!\bigl(\sqrt{n}\lg n\bigr) \]

---

c.

\[ T(n) = 2T\!\left(\tfrac{n}{4}\right) + \sqrt{n}\,\lg^{2}n \]

1. 分析：

   • \(f(n) = \sqrt{n}\,\lg^2 n\)
   • 比较 \(f(n) = \sqrt{n}\,\lg^2 n\) 和 \(n^{\log_b a} = \sqrt{n}\)。
   • \(f(n)\) 的增长速度比 \(n^{\log_b a}\) 要快，但它只是快了一个对数因子（\(\lg^2 n\)），并不是多项式级别的快。因此，它不满足情况三的条件。
   • 我们再来看情况二的通用形式：\(f(n) = \Theta\!\bigl(n^{\log_b a}\log^k n\bigr)\)。
   • 这里，\(f(n) = \Theta\!\bigl(\sqrt{n}\log^2 n\bigr)\)，即 \(k = 2\)。
   • 这依然符合主方法的 情况二 (Case 2)。 2. 结论：
   • 总成本需要在原有基础上追加一个对数因子。
   • \[ T(n) = \Theta\!\bigl(n^{\log_b a}\log^{k+1} n\bigr) = \Theta\!\bigl(\sqrt{n}\log^{2+1} n\bigr) = \Theta\!\bigl(\sqrt{n}\lg^3 n\bigr) \]

---

d.

\[ T(n) = 2T\!\left(\tfrac{n}{4}\right) + n \]

1. 分析：

   • \(f(n) = n\)
   • 比较 \(f(n) = n\) 和 \(n^{\log_b a} = \sqrt{n}\)。
   • \(f(n)\) 的增长速度远快于 \(\sqrt{n}\)。严格来说，\(f(n) = n^1 = \Omega(n^{0.5+\varepsilon})\)，我们可以取 \(\varepsilon = 0.5\)。
   • 这满足了主方法的 情况三 (Case 3) 的第一个条件。
   • 我们还需要检查正则条件：\(a f(n/b) \leq c f(n)\) 是否对某个 \(c < 1\) 成立。
     • \(2 \cdot f(n/4) \leq c \cdot n\)
     • \(2 \cdot (n/4) \leq c \cdot n\)
     • \(n/2 \leq c \cdot n\)
     • \(1/2 \leq c\)
   • 我们可以选择 \(c = 1/2\)（或 \(0.6, 0.9\) 等），这满足 \(1/2 \leq c < 1\)。所以正则条件成立。 2. 结论：
   • 总成本由 \(f(n)\) 决定。
   • \[ T(n) = \Theta(f(n)) = \Theta(n) \]

---

e.

\[ T(n) = 2T\!\left(\tfrac{n}{4}\right) + n^2 \]

1. 分析：

   • \(f(n) = n^2\)
   • 比较 \(f(n) = n^2\) 和 \(n^{\log_b a} = \sqrt{n}\)。
   • \(f(n)\) 的增长速度远快于 \(\sqrt{n}\)。严格来说，\(f(n) = n^2 = \Omega(n^{0.5+\varepsilon})\)，我们可以取 \(\varepsilon = 1.5\)。
   • 这同样满足主方法的 情况三 (Case 3) 的第一个条件。
   • 我们再检查正则条件：\(a f(n/b) \leq c f(n)\) 是否对某个 \(c < 1\) 成立。
     • \(2 \cdot f(n/4) \leq c \cdot n^2\)
     • \(2 \cdot (n/4)^2 \leq c \cdot n^2\)
     • \(2 \cdot (n^2/16) \leq c \cdot n^2\)
     • \(n^2/8 \leq c \cdot n^2\)
     • \(1/8 \leq c\)
   • 我们可以选择 \(c = 1/8\)（或 \(0.5, 0.9\) 等），这满足 \(1/8 \leq c < 1\)。所以正则条件也成立。 2. 结论：
   • 总成本由 \(f(n)\) 决定。
   • \[ T(n) = \Theta(f(n)) = \Theta(n^2) \]

.

递归树法

对于不满足主定理条件的递归式，可以尝试用递归树法。

我整理了递归树方法的一般化总结，对于递归形式：

\[ T(n) = A \cdot T\left(\frac{n}{B}\right) + w(n) \]

符号	含义
\(A\)	每层递归产生的子问题数量
\(B\)	每个子问题的规模相对于原问题规模的缩减因子
\(w(n)\)	划分 (Divide) 和合并 (Combine) 阶段的工作量（非递归部分）

对于Level 0，也就是根节点，其节点数是1，工作量是\(w(n)\)。

对于Level i，也就是任意层，其节点数是\(A^i\)，每个节点的规模是\(n/B^i\)，每个节点的工作量是\(w(n/B^i)\)，该层的总工作量\(C^i\)是：

\[ C_i = (\text{节点数}) \times (\text{单个节点工作量}) = A^i \cdot w\left(\frac{n}{B^i}\right) \]

树的高度\(h\)的确定条件是递归在达到基准情况（Base Case），即子问题规模变为 \(1\) 时终止。设 \(n/B^h = 1\)，则高度为：

\[ B^h = n \implies h = \log_B n \]

接着确定叶子的数量，确定条件是所有叶子都在高度 \(h\) 处，那么叶子节点数等于 \(A\) 的 \(h\) 次方：

\[ \text{叶子数} = A^h = A^{\log_B n} \]

利用换底公式\(a^{\log_b c} = c^{\log_b a}\)：

\[ \text{叶子数} = n^{\log_B A} \]

计算叶子总成本，叶子处的总工作量，通常是基准情况的成本乘以叶子数量。其表示为\(\Theta(\text{叶子数} \times \text{基准情况成本})\)。如果基准情况成本为 \(\Theta(1)\)，则：

\[ \text{叶子总成本} = \Theta(n^{\log_B A}) \]

最后计算总工作量\(T(n)\)，总工作量是所有非叶子级别的工作量之和，加上叶子级别的总成本。

\[ \text{总工作量 } T(n) = \sum_{i=0}^{h-1} (\text{Level } i \text{ 的总成本}) + (\text{叶子总成本}) \]

也即：

\[ T(n) = \underbrace{\sum_{i=0}^{\log_B n - 1} A^i \cdot w\left(\frac{n}{B^i}\right)}_{\text{非叶子节点工作量之和}} + \underbrace{\Theta(n^{\log_B A})}_{\text{叶子节点总成本}} \]

对比上式的左右两边贡献的工作量，对比后找到主导项，占据主导地位的就是最终的时间复杂度。这种一般化总结是Master Method 背后的理论基础。当 \(w(n)\) 是多项式时，我们可以直接使用 Master Method 的三条情况来避免复杂的求和运算。

---

示例

以QuickSort的递归式为例，我们来看一下如何使用递归树法。

对于递归式：

\[ T(n) = T\left(\frac{n}{4}\right) + T\left(\frac{3n}{4}\right) + \Theta(n) \]

由于主方法要求所有子问题具有相同的规模，即 \(T(n) = aT(n/b) + f(n)\) 的形式。本递归式中的子问题规模分别为 \(n/4\) 和 \(3n/4\)，不相等。递归树是一种通用的可视化方法，尤其适用于子问题规模不等的递归关系，可以清晰地展示每层的工作量和树的高度，因此我们用递归树来解决该式子。

可以看到，递归树是不平衡的，两个递归调用 \(T(n/4)\) 和 \(T(3n/4)\) 产生的子问题规模不相等：

• \(T(n/4)\) 分支的问题规模下降更快
• \(T(3n/4)\)分支的问题规模下降更慢，因此会形成更深的路径

我们可以分析最短路径、最长路径和树的总高度。

最短路径 (Shortest Path/Depth): 由问题规模下降最快的子分支 \(T(n/4)\) 决定。最短深度 \(k_{shortest}\) 是使问题规模降至基线情况（如 1）的深度。

\[ \frac{n}{4^{k_{shortest}}} = 1 \implies k_{shortest} = \log_4 n \]

最长路径 (Longest Path/Height): 由问题规模下降最慢的子分支 \(T(3n/4)\) 决定。最长深度 \(k_{longest}\) 是使问题规模降至基线情况（如 1）的深度。

\[ \left(\frac{3}{4}\right)^{k_{longest}} n = 1 \implies k_{longest} = \log_{4/3} n \]

树的总高度: \(h = \Theta(\log n)\) (因为 \(\log_{4/3} n\) 和 \(\log_4 n\) 都属于 \(\Theta(\log n)\))

---

每层完整级别的工作量：

• Level 0 (根节点): 成本为 \(cn\).
• Level 1: 子问题规模为 \(n/4\) 和 \(3n/4\).
  • 总成本: \(c\left(\frac{n}{4}\right) + c\left(\frac{3n}{4}\right) = c\left(\frac{n}{4} + \frac{3n}{4}\right) = c n\).
• Level 2: 子问题规模为 \(n/16, 3n/16, 3n/16, 9n/16\).
  • 总成本: \(c\left(\frac{n}{16}\right) + c\left(\frac{3n}{16}\right) + c\left(\frac{3n}{16}\right) + c\left(\frac{9n}{16}\right) = c\left(\frac{1+3+3+9}{16}\right)n = c\left(\frac{16}{16}\right)n = c n\).
• 观察到的模式: 在所有完整的级别上，工作量都是 \(\mathbf{cn}\) 或 \(\mathbf{\Theta(n)}\)。

正式证明 (Justification):

对于任意级别 \(i\)（从 \(i=0\) 到最短深度 \(\log_4 n\)），该级别上的所有节点表示的子问题规模之和始终为 \(n\).

一个节点在第 \(i\) 层，它是由从根到它所经过的 \(j\) 个 \(n/4\) 分裂和 \(i-j\) 个 \(3n/4\) 分裂产生的，其问题规模为 \(\left(\frac{1}{4}\right)^j \left(\frac{3}{4}\right)^{i-j} n\).

该层工作量 \(\text{Cost}_{\text{level } i}\) 是所有节点成本之和：

\[ \text{Cost}_{\text{level } i} = \sum_{j=0}^{i} \begin{pmatrix} i \\ j \end{pmatrix} \cdot c \cdot \left(\frac{1}{4}\right)^j \left(\frac{3}{4}\right)^{i-j} n \]

将 \(cn\) 提出来：

\[ \text{Cost}_{\text{level } i} = c n \sum_{j=0}^{i} \begin{pmatrix} i \\ j \end{pmatrix} \left(\frac{1}{4}\right)^j \left(\frac{3}{4}\right)^{i-j} \]

根据二项式定理 \(\sum_{j=0}^{i} \begin{pmatrix} i \\ j \end{pmatrix} x^j y^{i-j} = (x+y)^i\)，其中 \(x=1/4\) 且 \(y=3/4\):

\[ \text{Cost}_{\text{level } i} = c n \left(\frac{1}{4} + \frac{3}{4}\right)^i = c n \cdot (1)^i = \mathbf{cn} \]

这证实了在所有完整的级别上，总工作量始终为 \(cn\) 或 \(\mathbf{\Theta(n)}\)。

---

猜测 (Guess)：

• 工作量/层: \(\Theta(n)\)
• 层数/高度: \(\Theta(\log n)\) (由最长路径 \(\log_{4/3} n\) 决定)
• 总工作量: (工作量/层) \(\times\) (层数) \(\approx \Theta(n) \times \Theta(\log n) = \mathbf{\Theta(n \log n)}\)

1、证明上界 \(O(n \log n)\)****

目标: 证明 \(T(n) \le c_2 n \log n\) 成立，其中 \(c_2 > 0\) 和 \(n_0\) 为常数。

归纳假设: 假设对于所有 \(k < n\)，有 \(T(k) \le c_2 k \log k\) 成立。

代入与推导:

\[ T(n) = T\left(\frac{n}{4}\right) + T\left(\frac{3n}{4}\right) + \Theta(n) \]

\[ \le c_2 \left(\frac{n}{4}\right) \log \left(\frac{n}{4}\right) + c_2 \left(\frac{3n}{4}\right) \log \left(\frac{3n}{4}\right) + d_2 n \]

\[ \le c_2 \frac{n}{4} (\log n - \log 4) + c_2 \frac{3n}{4} (\log n - \log (4/3)) + d_2 n \]

\[ \text{（简化，使用 } \log 4 = 2 \text{ 和 } \log (4/3) \approx 0.415 \text{）} \]

\[ = c_2 \log n \left(\frac{n}{4} + \frac{3n}{4}\right) - c_2 n \left(\frac{2}{4} + \frac{3}{4} \log (4/3)\right) + d_2 n \]

\[ = c_2 n \log n - c_2 n \left(\frac{1}{2} + \frac{3}{4} (2 - \log_2 3)\right) + d_2 n \]

\[ = c_2 n \log n - n \left[c_2 \left(\frac{1}{2} + \frac{3}{4} (2 - \log_2 3)\right) - d_2\right] \]

验证:

为了使 \(T(n) \le c_2 n \log n\) 成立，我们要求被减去的项 非负：

\[ n \left[c_2 \left(\frac{1}{2} + \frac{3}{4} (2 - \log_2 3)\right) - d_2\right] \ge 0 \]

\[ \implies c_2 \left(\frac{1}{2} + \frac{3}{4} (2 - \log_2 3)\right) - d_2 \ge 0 \]

括号内的项是一个正常数 (近似 0.811)。因此，我们总可以选择一个足够大的常数 \(c_2\) (具体地， \(c_2 \ge d_2 / 0.811\)) 来满足这个不等式。

因此，上界 \(O(n \log n)\) 成立。

2、证明下界 \(\Omega(n \log n)\)****

目标: 证明 \(T(n) \ge c_1 n \log n\) 成立，其中 \(c_1 > 0\) 和 \(n_0\) 为常数。

归纳假设: 假设对于所有 \(k < n\)，有 \(T(k) \ge c_1 k \log k\) 成立。

代入与推导:

\[ T(n) = T\left(\frac{n}{4}\right) + T\left(\frac{3n}{4}\right) + \Theta(n) \]

\[ \ge c_1 \left(\frac{n}{4}\right) \log \left(\frac{n}{4}\right) + c_1 \left(\frac{3n}{4}\right) \log \left(\frac{3n}{4}\right) + d_1 n \]

\[ \text{（使用与上界证明相似的代数简化）} \]

\[ = c_1 n \log n - n \left[c_1 \left(\frac{1}{2} + \frac{3}{4} (2 - \log_2 3)\right) - d_1\right] \]

\[ = c_1 n \log n - c_1 n \left(\frac{1}{2} + \frac{3}{4} (2 - \log_2 3)\right) + d_1 n \]

验证:

为了使 \(T(n) \ge c_1 n \log n\) 成立，我们要求被减去的项 非正：

\[ c_1 n \left(\frac{1}{2} + \frac{3}{4} (2 - \log_2 3)\right) - d_1 n \le 0 \]

\[ \implies c_1 \left(\frac{1}{2} + \frac{3}{4} (2 - \log_2 3)\right) - d_1 \le 0 \]

括号内的项仍是正常数 (近似 0.811)。因此，我们总可以选择一个足够小的正常数 \(c_1\) (具体地， \(0 < c_1 \le d_1 / 0.811\)) 来满足这个不等式。

因此，下界 \(\Omega(n \log n)\) 成立。

由于我们成功证明了上界 \(T(n) = O(n \log n)\) 和下界 \(T(n) = \Omega(n \log n)\)，我们可以得出紧界为：

\[ \mathbf{T(n) = \Theta(n \log n)} \]

这表明，即使 Quicksort 的枢轴选择不平衡（如 \(n/4\) vs \(3n/4\) 的分割），其渐近运行时间仍然与平衡分割（如 \(n/2\) vs \(n/2\)）或平均情况下的 \(\Theta(n \log n)\) 保持一致。

代入法

代入法（Substitution Method）是最严谨的求解方法，可用于验证其他方法猜测出的解，可适用于所有的递归式。

然而，代入法必须先猜测递归式。一般我们会通过画出递归树，来更好地猜测递归式。猜测后，我们就需要用数学归纳法来证明这个猜测是正确的：

1. 归纳假设： 假设对于所有 \(m < n\)，\(T(m) \le c g(m)\) 成立（其中 \(c\) 是一个常数）。
2. 证明： 将归纳假设代入原递归式中，证明 \(T(n) \le c g(n)\) 也成立。
3. 检查基础情况： 确保基础情况（如 \(T(1)\)）也满足假设。

代入法一般用在主定理和递归树法无法处理的复杂情况中。在实际应用中，我们通常首先尝试使用主定理 。如果主定理不适用，就使用递归树法来猜测解，然后用代入法进行严格证明。

---

例解

a.

\[ T(n) = T(n-1) + n \quad \Rightarrow \quad T(n) = O(n^2) \]

1. 明确目标： 我们要证明 \(T(n) = O(n^2)\)。 根据定义，我们需要找到常数 \(c > 0\) 和 \(n_0\)，使得对于所有 \(n \geq n_0\)，都有

\[ T(n) \leq c n^2 \]

成立。

2. 归纳假设： 假设对于所有小于 \(n\) 的值 \(k\)，结论都成立。即：

\[ T(k) \leq c k^2 \]

特别地，对于 \(k = n-1\)：

\[ T(n-1) \leq c(n-1)^2 \]

3. 代入并推导： 将归纳假设代入原递归式：

\[ \begin{aligned} T(n) &= T(n-1) + n \\[6pt] &\leq c(n-1)^2 + n \\[6pt] &= c(n^2 - 2n + 1) + n \\[6pt] &= c n^2 - 2cn + c + n \end{aligned} \]

4. 验证结论： 我们的目标是证明上式 \(\leq c n^2\)：

\[ c n^2 - 2cn + c + n \;\leq\; c n^2 \]

化简得：

\[ -2cn + c + n \leq 0 \quad \Longleftrightarrow \quad n(1 - 2c) + c \leq 0 \]

为了让这个不等式对足够大的 \(n\) 恒成立，\(n\) 的系数 \((1-2c)\) 必须为负。

• \(1 - 2c < 0 \;\;\Longleftrightarrow\;\; c > 1/2\)

因此，只要我们选择 \(c > 1/2\)（例如 \(c=1\)），当 \(n\) 足够大时，这个式子就恒成立。

5. 结论： 我们成功找到了满足条件的常数（例如 \(c=1\)），因此证明了：

\[ T(n) = O(n^2) \]

---

b.

\[ T(n) = T(n/2) + \Theta(1) \quad \Rightarrow \quad T(n) = O(\lg n) \]

1. 明确目标： 我们将 \(\Theta(1)\) 写为常数 \(d\)。目标是证明存在常数 \(c > 0\) 和 \(n_0\)，使得对于 \(n \geq n_0\)，都有

\[ T(n) \leq c \lg n. \]

2. 归纳假设： 假设对于所有 \(k < n\)，都有

\[ T(k) \leq c \lg k. \]

3. 代入推导：

\[ \begin{aligned} T(n) &= T(n/2) + d \\[6pt] &\leq c \lg (n/2) + d \\[6pt] &= c(\lg n - 1) + d \\[6pt] &= c \lg n - c + d \end{aligned} \]

4. 验证结论： 我们需要证明

\[ c \lg n - c + d \leq c \lg n, \]

这需要 \(-c + d \leq 0\)，即

\[ c \geq d. \]

只要我们选择的证明常数 \(c\) 大于等于 \(o(1)\) 中的常数 \(d\)，归纳就成立。

---

c.

\[ T(n) = 2T(n/2) + n \quad \Rightarrow \quad T(n) = \Theta(n \lg n) \]

我们需要分别证明 \(O(n \lg n)\) 和 \(\Omega(n \lg n)\)。

证明上界 \(O(n \lg n)\)：

1. 目标： 证明 \(T(n) \leq c_2 n \lg n\)。
2. 假设： 对 \(k < n\)，有 \(T(k) \leq c_2 k \lg k\)。

3. 代入：

   $$ T(n) \leq 2\bigl(c_2 (n/2) \lg (n/2)\bigr) + n = c_2 n \lg n - c_2 n + n $$ 4. 验证： 我们需要

   $$ c_2 n \lg n - c_2 n + n \leq c_2 n \lg n, $$

   即 \(-c_2 n + n \leq 0\)，这要求 \(c_2 \geq 1\)。

证明下界 \(\Omega(n \lg n)\)：

1. 目标： 证明 \(T(n) \geq c_1 n \lg n\)。
2. 假设： 对 \(k < n\)，有 \(T(k) \geq c_1 k \lg k\)。

3. 代入：

   $$ T(n) \geq 2\bigl(c_1 (n/2) \lg (n/2)\bigr) + n = c_1 n \lg n - c_1 n + n $$ 4. 验证： 我们需要

   $$ c_1 n \lg n - c_1 n + n \geq c_1 n \lg n, $$

   即 \(-c_1 n + n \geq 0\)，这要求 \(c_1 \leq 1\)。

结论： 因为我们既可以证明上界，也可以证明下界，所以

\[ T(n) = \Theta(n \lg n) \]

成立。

---

d.

\[ T(n) = 2T(n/2 + 17) + n \quad \Rightarrow \quad T(n) = O(n \lg n) \]

1. 明确目标： 证明存在常数 \(c > 0\) 和 \(n_0\)，使得

\[ T(n) \leq c n \lg n. \]

2. 归纳假设： 假设对所有 \(k < n\)，都有

\[ T(k) \leq c k \lg k. \]

3. 代入推导：

\[ T(n) \leq 2\bigl(c(n/2 + 17)\lg(n/2 + 17)\bigr) + n \]

这里的 \(+17\) 比较棘手，但对于足够大的 \(n\)，它是一个低阶项。我们可以观察到 \(n/2 + 17\) 不会比 \(n\) 大，并且 \(\lg\) 是一个增长很慢的函数。我们可以放心地说，对于足够大的 \(n\)：

\[ c(n/2 + 17)\lg(n/2 + 17) \approx c(n/2)\lg(n/2) \]

因此，代数推导过程与上一个问题 \(c\) 非常相似：

\[ T(n) \leq c n \lg n - c n + n + (\text{一些低阶项}) \]

4. 验证结论： 为了使不等式成立，我们需要 \(-cn\) 能够“压制”住 \(+n\) 和其他所有因 \(+17\) 产生的低阶项。只要 \(n\) 足够大，\(-cn + n\) 这一项是主导的。因此，我们只需要

\[ -cn + n \leq 0 \quad \Rightarrow \quad c \geq 1 \]

选择一个足够大的 \(c\) 即可。

---

e.

\[ T(n) = 2T(n/3) + \Theta(n) \quad \Rightarrow \quad T(n) = \Theta(n) \]

我们将 \(\Theta(n)\) 写为 \(dn\)。

证明下界 \(\Omega(n)\)： 这一步很简单，因为递归式中包含了 \(+dn\) 这一项，所以 \(T(n)\) 至少是 \(dn\)，因此

\[ T(n) = \Omega(n) \]

天然成立。

证明上界 \(O(n)\)：

1. 目标： 证明 \(T(n) \leq cn\)。
2. 假设： 对 \(k < n\)，有 \(T(k) \leq ck\)。

3. 代入：

   $$ \begin{aligned} T(n) &= 2T(n/3) + dn \[6pt] &\leq 2\bigl(c(n/3)\bigr) + dn \[6pt] &= (2c/3)n + dn \[6pt] &= (2c/3 + d)n \end{aligned} $$ 4. 验证： 我们需要

   $$ (2c/3 + d)n \leq cn, $$

   即

   $$ 2c/3 + d \leq c. $$

   • \(d \leq c - 2c/3 \;\;\Rightarrow\;\; d \leq c/3 \;\;\Rightarrow\;\; c \geq 3d\)。
   • 只要我们选择的 \(c\) 至少是 \(d\) 的 3 倍，证明就成立。

结论： 因为上下界都成立，所以

\[ T(n) = \Theta(n). \]

---

f.

\[ T(n) = 4T(n/2) + \Theta(n) \quad \Rightarrow \quad T(n) = \Theta(n^2) \]

我们将 \(\Theta(n)\) 写为 \(dn\)。

证明下界 \(\Omega(n^2)\)：

1. 目标： 证明 \(T(n) \geq c_1 n^2\)。
2. 假设： 对 \(k < n\)，有 \(T(k) \geq c_1 k^2\)。
3. 代入： $$ T(n) \geq 4\bigl(c_1 (n/2)^2\bigr) + dn = c_1 n^2 + dn $$
4. 验证： 我们需要 \(c_1 n^2 + dn \geq c_1 n^2\)。因为 \(dn\) 是正数，这个不等式显然成立。

证明上界 \(O(n^2)\)：

1. 目标： 证明 \(T(n) \leq c_2 n^2\)。
2. 假设： 对 \(k < n\)，有 \(T(k) \leq c_2 k^2\)。

3. 代入：

   $$ T(n) \leq 4\bigl(c_2 (n/2)^2\bigr) + dn = c_2 n^2 + dn $$ 4. 验证： 我们需要 \(c_2 n^2 + dn \leq c_2 n^2\)，即 \(dn \leq 0\)，这不可能成立。证明失败。 5. 强化假设： 我们尝试证明

   $$ T(n) \leq c_2 n^2 - c_3 n. $$ 6. 新假设： 对 \(k < n\)，有 \(T(k) \leq c_2 k^2 - c_3 k\)。 7. 新代入：

   $$ \begin{aligned} T(n) &\leq 4\bigl(c_2 (n/2)^2 - c_3 (n/2)\bigr) + dn \[6pt] &= c_2 n^2 - 2c_3 n + dn \end{aligned} $$ 8. 新验证： 我们需要

   $$ c_2 n^2 - 2c_3 n + dn \leq c_2 n^2 - c_3 n, $$

   即

   $$ -2c_3 n + dn \leq -c_3 n \quad \Rightarrow \quad dn \leq c_3 n \quad \Rightarrow \quad c_3 \geq d. $$

   只要我们选择的常数 \(c_3\) 大于等于 \(d\)，证明就成立。

结论： 因为上下界都成立，所以

\[ T(n) = \Theta(n^2). \]

.

排序算法

大多数人学习排序算法第一个接触的算法是选择排序（Selection Sort）。选择排序的思路很直观、很简单：

每一轮从未排序区间中，选出最小（或最大）元素，放到已排序区间的末尾。

无论数据是有序还是乱序，比较次数都不会减少。因此选择排序的最好、平均以及最坏时间复杂度均为O(n²)。并且由于选择会交换位置，因此这是一个不稳定的排序方法，并且由于其效率非常低，因此在实践中我们并不会使用该方法。本章节我们来学习一些实践中非常重要的排序方法。

稳定排序

我们把排序后相同元素前后相对位置不变的排序方法叫做稳定排序。

冒泡排序

插入排序

归并排序

计数排序

基数排序

桶排序

堆排序

堆的数据结构参见Tree笔记。

快速排序

快速排序因为很快，所以叫快速排序。然而，对于包含输入size为n的数组来说，快速排序的最坏情况时间复杂度依然是\(O(n^2)\)。虽然理论上的最坏情况很差，但是快速排序依然是实际排序应用中最好的选择。

快速排序的核心思想是分治：

对于一个要排序的队列，先找到一个学生做标杆（pivot），然后让所有比标杆矮的以及相等的站在左边，所有比标杆高的站到右边。

对标杆左边的部分，递归应用同样的方式；对标杆右边的部分，递归应用同样的方式。直到每组只剩一个人或没有人为止，队列就排好了。

依据选取Pivot的不同方式，分为：

• 固定首尾
• 随机pivot
• 三数取中

依据按照pivot分区的方法，分为：

• Lomuto分区方案
• Hoare分区方案
• 三路快排

关于上述不同pivot选取方式和不同的分区方法，我们后面会详细介绍。教学中一般普通快排选择的方案是Lomuto分区方案，也就是用一个单指针进行交换，其代码如下：（因为快排很重要，所以我们就直接记住代码，跳过伪代码）

# 普通快速排序（Lomuto分区方案）

def quicksort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high) # 获取分区点pivot
        quicksort(arr, low, pivot-1) # 递归pivot左边的部分
        quicksort(arr, pivot+1, high) # 递归pivot右边的部分

def partition(arr, low, high):
    pivot = arr[high] # 选取最后一个元素作为基准pivot
    i = low - 1 # 在Lumuto分区法中，i就是比pivot小的区域的边界，所以一开始在界外

    for j in range(low, high):
        if arr[j] < = pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i] # 维护边界

    arr[i+1], arr[high] = arr[high], arr[i+1] # 把pivot放回正确的位置：边界的右侧
    return i+1

我们来看一下普通快速排序的性能，设 \(T(n)\) 为排序 \(n\) 个元素所需的时间，则基本的递归式是：

\[ T(n) = T(\text{左边数量}) + T(\text{右边数量}) + \Theta(n) \]

\(\Theta(n)\) 是 partition 函数的时间，因为它必须要把这一层的所有数字扫描一遍。

（1）最差情况（worst case）的时间复杂度

假设数组已经排好序或者数组里全是重复的元素，那么将high作为pivot会导致切分后所有的pivot左边的数字依然会待在左边，从而导致递归式变成了一个链表形状：

\[ T(n) = T(n-1) + T(0) + \Theta(n) = T(n-1) + n \]

这相当于计算等差数列求和：\(n + (n-1) + (n-2) + ... + 1\)。结果是 \(\frac{n(n+1)}{2}\)，也就是 \(O(n^2)\) 。

（2）最好情况（best case）的时间复杂度

这是最理想的情况：每次pivot正好把数组分成了两个部分：

\[ T(n) = 2T(n/2) + \Theta(n) \]

根据主定理（Master Theorem），或者类比归并排序，树的高度是 \(\log_2 n\)，每层的工作量是 \(n\)，因而结果是 \(O(n \log n)\) 。

（3）平均情况（average case）的时间复杂度

我们不太容易直接算出平均的情况，因此CLRS算法书中在这里给出了一个低于实际情况运行的9：1划分方式：

\[ T(n) = T(n/10) + T(9n/10) + \Theta(n) \]

这种划分不够平衡，树非常歪，左边短右边长，但是树的高度依然是对数级别的（最深也就是 \(\log_{10/9} n\)）。在数学上，\(\log_{10/9} n\) 和 \(\log_2 n\) 只是差了一个常数倍数而已。因此即便是9：1的不平衡划分方式，普通快排的平均复杂度依然是 \(O(n \log n)\)。

（4）空间复杂度

在上面的代码示例中，我们使用了原地排序的方法，看起来没有额外开辟数组，但 递归调用是有代价的 （系统栈 Stack）。

在最好/平均情况下，递归树高度为 \(\log n\)，所以空间复杂度是 \(O(\log n)\) 。

在最坏情况下，递归树退化成链表形状，高度为 \(n\)，所以空间复杂度是 \(O(n)\) 。（如果不做尾递归优化的话，会有栈溢出风险）。

这里退化成链表指的是递归栈的形状，比如说，当递归调用非常均衡时，函数调用的层级关系如下：

                 [ 处理 100 个数 ]
                 /             \
       [ 处理 50 个 ]         [ 处理 50 个 ]
       /        \             /        \
  [25个]       [25个]      [25个]      [25个]

然而，假设我们遇到了最坏情况，那么就会变成链表一样的：

[ 处理 5 个数 ]
    |
    ↓
[ 处理 4 个数 ]   (右边是空的，不用管)
    |
    ↓
[ 处理 3 个数 ]
    |
    ↓
[ 处理 2 个数 ]
    |
    ↓
[ 处理 1 个数 ]

在物理上，数据还在数组里，但是在逻辑上，每一个函数只呼叫了下一个函数，从而形成了一条单链。

随机快排

为了避免最差情况，我们可以使用随机化方法，随机选取Pivot。实现方法非常简单，就是在普通快排的基础上，在选取pivot之前随机选一个合法的坐标，然后交换该坐标的数字和原本要选取的最后一个数字即可：

# 随机快排
import random # 加入随机数

def quicksort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high) # 获取分区点pivot
        quicksort(arr, low, pivot-1) # 递归pivot左边的部分
        quicksort(arr, pivot+1, high) # 递归pivot右边的部分

def partition(arr, low, high):
    random_index = random.randint(low, high) # 随机选取一个下标
    arr[random_index], arr[high] = arr[high], arr[random_index]

    # --------下面是普通快排，原封不动即可
    pivot = arr[high] # 选取最后一个元素作为基准pivot
    i = low - 1 # 在Lumuto分区法中，i就是比pivot小的区域的边界，所以一开始在界外

    for j in range(low, high):
        if arr[j] < = pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i] # 维护边界

    arr[i+1], arr[high] = arr[high], arr[i+1] # 把pivot放回正确的位置：边界的右侧
    return i+1

我们来看一下随机快排的递归式。我们假设每一个数字被选为 Pivot 的概率都是 \(\frac{1}{n}\)，那么随机快排的递归式将是基于期望运行时间（Expected Running Time）描述的：

\[ T(n) = \frac{1}{n} \sum_{k=0}^{n-1} \big[ T(k) + T(n-k-1) \big] + \Theta(n) \]

虽然这个公式看着吓人，但通过数学推导（替换法或数学归纳法），它的解就是我们熟悉的：

\[ E[T(n)] = O(n \log n) \]

这里要注意，上面说的是期望时间复杂度。换句话说，即便使用了随机数，假设我们运气超级差，依然可能会遇到连续的最差情况，从而导致最差时间复杂度为\(O(n^2)\)。当然，这种理论在现实中几乎很难出现，因为随着层数的增加，最差情况发生概率将趋近于0。

---

另外，在学校的教程中，随机快排的递归式如下：

\[ T(n) = \frac{1}{n} \sum_{k=0}^{n-1} [T(k) + T(n-k-1)] + \Theta(n) \]

随机快排平均运行时间的标准形式如下：

\[ T_{avg}(n) = \frac{2}{n} \sum_{k=1}^{n-1} T_{avg}(k) + \Theta(n) \]

上式中的2/n系数中的2来自于概率空间中的对称性。

三路取中

三路取中（Median-of-Three） 和随机快排一样，是针对pivot选择方案的。在工业界，三路取中往往效果好于随机快排。这是因为随机数在计算机底层是一个很贵的操作，需要复杂的数学运算。同时，三路取中是确定性的，可以方便调试。

和随机快排一样，三路取中也是在pivot选取之前增加一个比较三路然后取中并交换就可以，实现起来非常简单：

# 三路取中

def quicksort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        quicksort(arr, low, pivot-1)
        quicksort(arr, pivot+1, high)

def partition(arr, low, high):
    # 三路取中
    mid = (low + high) // 2

    # 先让 low 成为最小的那个
    if arr[low] > arr[mid]:
        arr[low], arr[mid] = arr[mid], arr[low]
    if arr[low] > arr[high]:
        arr[low], arr[high] = arr[high], arr[low]

    # 接着让 high 成为中间的那个
    if arr[high] > arr[mid]:
        arr[mid], arr[high] = arr[high], arr[mid]

    # ---------下面是原封不动的普通快排（Lomuto分区方案）
    pivot = arr[high] 
    i = low - 1 

    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

三路取中的核心目的就是让 Pivot 更大概率接近数组的 真实中位数 ，从而让左右划分更均匀（接近 1:1）。理想情况下，递归式将更加接近均匀划分：

\[ T(n) = 2T(n/2) + \Theta(n) \]

然而，三路取中在数学上的最坏情况依然是\(O(n^2)\)。

在实践中，普通的随机快排递归式常数项大概是 \(2n \ln n \approx 1.39n \log_2 n\) 。 三路取中优化后的常数项会降低到约 \(1.18n \log_2 n\) 左右，也就是比普通随机快了约15%~20%。

这个1.18并非随便估计出来的，而是通过解一个复杂的递归式得出的精确解。设 \(C_n\) 是排序 \(n\) 个元素所需的比较次数：

\[ C_n = (n + 1) + \sum_{k=1}^{n} P(pivot=k) \times (C_{k-1} + C_{n-k}) \]

这里最关键的是 \(P(pivot=k)\)（选中第 \(k\) 小的元素做基准的概率）：在三路取中里，只有当选出的三个样本中，一个小于 \(k\)，一个大于 \(k\)，且\(k\)自身被选中时，\(k\) 才会成为中位数。这是一个组合数学问题，其概率为：

\[ P(pivot=k) = \frac{(k-1)(n-k)}{\binom{n}{3}} \]

其含义是：从比 \(k\) 小的 \(k-1\) 个里选1个，从比 \(k\) 大的 \(n-k\) 个里选1个，除以总共选3个的组合数。把这个概率代入递归式，经过极其复杂的数学变换（通常使用生成函数或微分方程求解），我们会得到比较次数的通项公式：

\[ C_n \approx \frac{12}{7} n \ln n \]

上面的公式是自然对数 \(\ln n\)。而我们在计算机科学里习惯说 \(\log_2 n\)。我们需要做一个换算：

\[ \ln n = \ln 2 \times \log_2 n \approx 0.693 \times \log_2 n \]

即可得到1.88：

\[ \frac{12}{7} \times 0.693 \times n \log_2 n \approx 1.714 \times 0.693 \times n \log_2 n \approx \mathbf{1.18} \ n \log_2 n \]

值得注意的是，三路取中会造成一个著名的安全漏洞，从而让黑客可以针对该漏洞专门构造一个针对三路取中的杀手序列（Killer Sequence），来让排序服务退化到\(O(n^2)\)，进而导致DoS拒绝服务供给。因此在更高安全要求的场景中，工业界会采用三路取中的升级版：九路取中（Tukey's Ninther），从而让黑客难以攻击。

MoM

Median of Medians (MoM)是快速排序中另一种pivot选择的策略，该策略可以保证快速排序在最坏情况下的时间复杂度为 \(O(n \log n)\)，与其平均时间复杂度相同。相比之下，传统的快速排序（例如随机快排或三路取中）在最坏情况下可能退化到 \(O(n^2)\)。不过请注意，MoM只是在理论上比三路取中更好，然而在实践中三路取中通常更好。

MoM 不直接寻找真实中位数，而是通过 分组 、 求中位数 、递归求中位数的中位数的方法，找到一个保证至少能排除掉 固定比例 （大于 30%）元素的近似中位数 \(p\)。

分组大小 \(g\) 的选择是 MoM 算法的关键，它必须满足一个数学条件，才能保证算法在线性时间内完成。要保证算法在 \(O(n)\) 时间内运行，递归关系式中的两个递归项相加必须严格小于 1：

\[ \text{递归项和} = \frac{1}{g} + \alpha < 1 \]

其中\(1/g\)是递归寻找“中位数的中位数” \(p\) 的子问题大小比例；\(\alpha\)是分区后，最坏情况下需要递归处理的子数组大小比例。

\(g=5\) 是满足这个条件的最小奇数分组大小，因此被选中以平衡分组内部排序的常数开销和递归调用的效率。如果 \(g=3\)： \(\alpha = 2/3\)。递归项和为 \(1/3 + 2/3 = 1\)。这导致时间复杂度为 \(O(n \log n)\)，不符合线性时间要求。

下面我们来看一下MoM的实现步骤。假设我们要在数组 \(A\) 中找到一个好的主元 \(p\)：

1. 分组 (Divide)： 将 \(n\) 个元素分成 \(\lceil n/5 \rceil\) 个小组，每组 5 个元素。
2. 求小组中位数 (Find Local Medians)： 对每个小组内部进行排序（例如插入排序），并确定其中位数 \(m_i\)。
3. 递归求 MoM (Recursive Call)： 递归地调用 MoM 算法，找出所有这些小组中位数 \(M = \{m_1, m_2, \ldots\}\) 的中位数 \(p\)。这个 \(p\) 就是我们最终的主元（“中位数的中位数”）。
4. 分区 (Partition)： 使用 \(p\) 对原始数组 \(A\) 进行分区操作，将 \(A\) 划分为小于 \(p\) (\(A_L\))、等于 \(p\) (\(A_E\)) 和大于 \(p\) (\(A_G\)) 三部分。
5. 返回主元： 将 \(p\) 作为主元，用于快速排序。

最后来看一下MoM选择算法本身的递归式（最坏情况）：

\[ T(n) = T(\lceil n/5 \rceil) + T(7n/10) + O(n) \]

以及使用MoM后，快速排序的最坏情况：

\[ T(n) = T(3n/10) + T(7n/10) + O(n) \]

该递归式求解后是\(T(n) = O(n \log n)\)，也就是说MoM可以让快速排序最差情况也不会退化到\(O(n^2)\)。

三路快排

三路快排不同于三路取中和随机快排，三路快排针对的是pivot选取之后的切分方法。

在普通快排和随机快排中，我们区分的是小于等于pivot和大于pivot的部分，也就是将数组切分成了两份，因此也叫做2-Way快排。二路快排的缺点就是如果有很多个和pivot一样大的数字，比如说如果有 100 万个 5，普通快排会把这些 5 甚至还会继续递归处理，非常浪费。

三路快排（3-Way QuickSort）就是把数组切分为三份：小于pivot、等于pivot、大于pivot的。这样一来，那些等于 Pivot 的部分，已经在正确位置了， 下一轮递归直接跳过它们 ，只排“小于”和“大于”的部分。这种处理方法在有大量重复元素的情况下非常好用。

双轴快排

Tim Sort

Tim Sort是现代排序实践中的集大成者，也是python内置的排序算法。

总结与对比

这里注意要总结一下常数项的对比，根据数学期望可以算出来：

• 普通随机快排\(\approx 1.386 n \log_2 n\)
• 归并排序\(\approx 1.0 \cdot n \log_2 n\)

然而，在实际使用中，快速排序的i是连续递增的，CPU 预取器能完美工作，数据早就在 L1 Cache 里等着了。这种比较极其廉价；而归并排序涉及从两个不同的数组段读数据并写入第三个辅助数组，内存吞吐压力大，Cache Miss 率相对较高。因此在实际运行速度比较中，快速排序比归并排序更快。

最后我们来分析一下排序算法的下界，………………

搜索

对于一个array，我们可以直接遍历整个array来一一确定是否有想要查找的符合要求的内容，其用时上界是array的长度。但是这显然太低效了。因此针对一些特别的情况，我们有特别的查找方法。

二分查找

二分查找思路非常简单，但是却有着惊人的应用广度。

经典应用

最小化最大值

问题 ：给定 \(N\) 个包裹和 \(K\) 艘船，要求将所有包裹分配给 \(K\) 艘船，使得所有船中 最大载重最小 。

最大化最小值

问题 ：给定一条长度为 \(L\) 的绳子，上面有 \(N\) 个标记点，需要从中剪出 \(K\) 段绳子，使得 最短那段绳子的长度最大 。

指数搜索

主要用于无界搜索问题（Unbounded Search），即当你不知道一个数组的长度时，你可以用指数快速确定该数组的长度。

快速选择

在算法理论中，SELECT通常指在一个无序列表中找到第 \(k\) 小（或第 \(k\) 大）的元素，即顺序统计量（Order Statistic）。

快速选择是快速排序的副产品，可以快速找到第k小的数。

随机快速选择

随机快排的：

\[ T_{avg}(n) = \frac{2}{n} \sum_{k=1}^{n-1} T_{avg}(k) + \Theta(n) \]

随机选择的：

\[ T_{exp}(n) \le \frac{2}{n} \sum_{k=n/2}^{n-1} T_{exp}(k) + \Theta(n) \]

.

常见基础算法

本章节介绍一些在LeetCode和面试等场景下常见的基础算法。本节介绍的主要是大多数人刚入门刷题的时候遇到的一些应用，稍微复杂一点的算法，如string、tree、graph、dp等方面的，都会在专门的章节中收录。

Boyer-Moore Majority Vote

Boyer-Moore 多数投票算法用于在一个数组中找到出现次数超过 \(\lfloor n/2 \rfloor\) 次的元素（即多数元素/Majority Element）。该算法的核心思想是抵消：不同的元素互相抵消，最终留下的就是多数元素。

算法步骤：

1. 维护一个候选人（candidate） 和一个计数器（count），初始 count 为 0。
2. 遍历数组：
   • 如果 count == 0，将当前元素设为新的候选人。
   • 如果当前元素等于候选人，count += 1。
   • 如果当前元素不等于候选人，count -= 1（抵消）。
3. 遍历结束后，候选人就是多数元素（前提是多数元素一定存在）。

def majority_element(nums):
    candidate, count = None, 0
    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1
    return candidate

时间复杂度：\(O(n)\)，只需遍历一次。空间复杂度：\(O(1)\)，只需要两个变量。

正确性直觉：多数元素出现次数超过 \(n/2\)，即使每次出现都被一个不同的元素抵消，它仍然会有剩余。因此最终留在候选人位置上的一定是多数元素。

如果不确定多数元素是否存在，需要第二轮遍历来验证候选人出现次数是否确实超过 \(n/2\)。

Prefix Sums

前缀和（Prefix Sum） 是一种预处理技巧，通过预先计算数组的累积和，将区间求和操作从 \(O(n)\) 优化到 \(O(1)\)。

一维前缀和

给定数组 nums[0..n-1]，构建前缀和数组 prefix[0..n]，其中：

\[ \text{prefix}[i] = \sum_{k=0}^{i-1} \text{nums}[k] \]

那么区间 \([l, r]\) 的元素之和可以用 \(O(1)\) 时间计算：

\[ \sum_{k=l}^{r} \text{nums}[k] = \text{prefix}[r+1] - \text{prefix}[l] \]

# 构建一维前缀和
def build_prefix(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    return prefix

# 查询区间 [l, r] 的和
def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]

二维前缀和

对于 \(m \times n\) 的矩阵，二维前缀和 prefix[i][j] 表示从 \((0,0)\) 到 \((i-1, j-1)\) 的子矩阵元素之和。利用容斥原理构建和查询：

\[ \text{prefix}[i][j] = \text{matrix}[i-1][j-1] + \text{prefix}[i-1][j] + \text{prefix}[i][j-1] - \text{prefix}[i-1][j-1] \]

查询子矩阵 \((r_1, c_1)\) 到 \((r_2, c_2)\) 的元素之和：

\[ \text{sum} = \text{prefix}[r_2+1][c_2+1] - \text{prefix}[r_1][c_2+1] - \text{prefix}[r_2+1][c_1] + \text{prefix}[r_1][c_1] \]

# 构建二维前缀和
def build_prefix_2d(matrix):
    m, n = len(matrix), len(matrix[0])
    prefix = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            prefix[i][j] = (matrix[i-1][j-1] + prefix[i-1][j]
                           + prefix[i][j-1] - prefix[i-1][j-1])
    return prefix

时间复杂度：预处理 \(O(n)\)（一维）或 \(O(mn)\)（二维），每次查询 \(O(1)\)。空间复杂度：\(O(n)\) 或 \(O(mn)\)。

Sliding Window

滑动窗口（Sliding Window） 是一种用于处理连续子数组/子串问题的技巧。其核心思想是维护一个窗口（通常用左右指针 left 和 right 表示），通过移动窗口边界来避免重复计算，将暴力的 \(O(n^2)\) 优化为 \(O(n)\)。

固定窗口大小

窗口大小固定为 \(k\)，窗口整体向右滑动。典型应用：大小为 \(k\) 的子数组的最大和。

# 固定窗口：求大小为 k 的子数组最大和
def max_sum_fixed(nums, k):
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # 右边进，左边出
        max_sum = max(max_sum, window_sum)
    return max_sum

可变窗口大小

窗口大小不固定，根据条件动态收缩或扩展。典型应用：满足某条件的最短/最长子数组。

通用模板：right 指针不断向右扩展窗口，当窗口内不满足条件时，移动 left 指针收缩窗口。

# 可变窗口：满足和 >= target 的最短子数组长度
def min_subarray_len(target, nums):
    left = 0
    window_sum = 0
    min_len = float('inf')
    for right in range(len(nums)):
        window_sum += nums[right]          # 扩展窗口
        while window_sum >= target:        # 满足条件时收缩
            min_len = min(min_len, right - left + 1)
            window_sum -= nums[left]
            left += 1
    return min_len if min_len != float('inf') else 0

时间复杂度：\(O(n)\)，因为 left 和 right 各自最多遍历数组一次。空间复杂度：\(O(1)\)（不考虑额外的哈希表等辅助结构）。

Two Pointers

双指针（Two Pointers） 是一种利用两个指针协同遍历数据结构的技巧，通常用于有序数组或链表问题中，能将 \(O(n^2)\) 的暴力搜索优化到 \(O(n)\)。

对向双指针（Opposite Direction）

两个指针分别从数组的两端出发，向中间靠拢。典型应用：有序数组中的 Two Sum、判断回文串、盛最多水的容器等。

# 有序数组中找到和为 target 的两个数
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1       # 和太小，左指针右移增大
        else:
            right -= 1      # 和太大，右指针左移减小
    return []

同向双指针（Same Direction）

两个指针从同一端出发，一个快一个慢。典型应用：移除有序数组中的重复元素、移动零等。

# 原地移除有序数组中的重复元素，返回新长度
def remove_duplicates(nums):
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

时间复杂度：\(O(n)\)，两个指针总共最多遍历数组一次。空间复杂度：\(O(1)\)。

滑动窗口本质上也是同向双指针的一种特殊应用。

Floyd's Cycle Detection

Floyd 判圈算法，又称龟兔赛跑算法（Tortoise and Hare Algorithm），用于检测链表中是否存在环（Cycle），并找到环的入口节点。

Phase 1: 检测环是否存在

使用快慢两个指针：慢指针（tortoise） 每次走 1 步，快指针（hare） 每次走 2 步。如果链表有环，快指针最终一定会追上慢指针（两者在环内相遇）；如果链表无环，快指针会先到达 None。

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True   # 存在环
    return False          # 不存在环

Phase 2: 找到环的入口

当快慢指针在环内相遇后，将其中一个指针重置到链表头部，然后两个指针都以每次 1 步的速度前进，它们再次相遇的地方就是环的入口节点。

数学证明：设链表头到环入口的距离为 \(a\)，环入口到相遇点的距离为 \(b\)，相遇点再绕回环入口的距离为 \(c\)。相遇时慢指针走了 \(a + b\) 步，快指针走了 \(a + b + k(b + c)\) 步（\(k\) 为快指针多绕的圈数）。由于快指针速度是慢指针的 2 倍：

\[ 2(a + b) = a + b + k(b + c) \implies a = k(b + c) - b = (k-1)(b+c) + c \]

因此 \(a \equiv c \pmod{b+c}\)，即从头节点和相遇点分别出发，走相同步数后会在环入口相遇。

def detect_cycle_entry(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:           # Phase 1: 找到相遇点
            slow = head            # Phase 2: 重置到头节点
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow            # 环的入口节点
    return None                    # 无环

时间复杂度：\(O(n)\)。空间复杂度：\(O(1)\)。

Group and Reverse in Linked List

K 个一组翻转链表（Reverse Nodes in k-Group） 是链表中的经典难题。给定一个链表，每 \(k\) 个节点为一组进行翻转，如果最后剩余的节点数不足 \(k\)，则保持原有顺序不变。

核心思路分为三步：

1. 检查当前位置开始是否还有 \(k\) 个节点。
2. 翻转当前这 \(k\) 个节点。
3. 递归/迭代处理剩余部分，并将翻转后的组与前后部分连接起来。

def reverse_k_group(head, k):
    # 1. 检查是否有 k 个节点
    curr = head
    count = 0
    while curr and count < k:
        curr = curr.next
        count += 1
    if count < k:
        return head  # 不足 k 个，不翻转

    # 2. 翻转前 k 个节点
    prev, curr = None, head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # 此时 prev 是翻转后的新头，head 是翻转后的新尾，curr 是下一组的头

    # 3. 递归处理剩余部分，并连接
    head.next = reverse_k_group(curr, k)
    return prev

翻转链表的基本操作是本题的基础。单链表翻转的核心就是逐个改变 next 指针的方向：

def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

时间复杂度：\(O(n)\)，每个节点被访问常数次。空间复杂度：递归版 \(O(n/k)\)（递归栈），迭代版 \(O(1)\)。

Hashing

对应CLRS11

哈希表（Hash Table） 是一种通过哈希函数（Hash Function） 将键（Key）映射到数组下标的数据结构，从而实现平均 \(O(1)\) 时间复杂度的插入、删除和查找操作。Python中的 dict 和 set 底层就是哈希表。

哈希函数

哈希函数 \(h(k)\) 将键 \(k\) 映射到哈希表中的一个槽位（slot）。一个好的哈希函数应当尽量将键均匀分布到各个槽位，以减少冲突。常见的哈希函数包括：

• 除法取余法（Division Method）：\(h(k) = k \mod m\)，其中 \(m\) 是表的大小，通常选择远离 2 的幂次的质数。
• 乘法取余法（Multiplication Method）：\(h(k) = \lfloor m \cdot (kA \mod 1) \rfloor\)，其中 \(0 < A < 1\)，Knuth 建议取 \(A \approx (\sqrt{5} - 1)/2 \approx 0.618\)。
• 全域哈希（Universal Hashing）：从一组哈希函数中随机选取，减少最坏情况下的碰撞概率。

冲突解决

当两个不同的键被映射到同一个槽位时，就发生了碰撞/冲突（Collision）。主要有两种解决方法：

1. 链接法（Chaining）

每个槽位维护一个链表（或其他动态数据结构），所有映射到同一槽位的元素都存储在该链表中。

• 插入：\(O(1)\)（直接在链表头部插入）
• 查找/删除：\(O(1 + \alpha)\)，其中 \(\alpha = n/m\) 是装载因子（Load Factor），\(n\) 是元素数量，\(m\) 是槽位数量
• 最坏情况：所有元素都映射到同一个槽位，退化为 \(O(n)\)

2. 开放寻址法（Open Addressing）

所有元素都直接存储在哈希表数组中。发生冲突时，按照某种探测序列（Probe Sequence） 寻找下一个可用的空槽位：

• 线性探测（Linear Probing）：\(h(k, i) = (h'(k) + i) \mod m\)，可能导致聚集（Clustering） 问题。
• 二次探测（Quadratic Probing）：\(h(k, i) = (h'(k) + c_1 i + c_2 i^2) \mod m\)，减轻聚集。
• 双重哈希（Double Hashing）：\(h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m\)，效果最好，分布最均匀。

# Python中哈希表的基本使用
hash_map = {}
hash_map["key1"] = "value1"          # 插入 O(1)
print(hash_map.get("key1", None))    # 查找 O(1)
del hash_map["key1"]                 # 删除 O(1)

# 用 set 进行去重和查找
seen = set()
seen.add(42)                         # O(1)
print(42 in seen)                    # O(1) 查找

操作	平均时间复杂度	最坏时间复杂度
插入	\(O(1)\)	\(O(n)\)
查找	\(O(1)\)	\(O(n)\)
删除	\(O(1)\)	\(O(n)\)

LC应用：Linear Structures/In-place Hashing

Bit Manipulation

位运算（Bit Manipulation） 直接操作整数的二进制位，速度极快，在算法优化和系统底层编程中广泛使用。

基本位运算符

运算符	名称	示例	说明
&	与（AND）	5 & 3 = 1	两位都为1时结果为1
\|	或（OR）	5 \| 3 = 7	至少一位为1时结果为1
^	异或（XOR）	5 ^ 3 = 6	两位不同时结果为1
~	取反（NOT）	~5 = -6	所有位取反
<<	左移	1 << 3 = 8	相当于乘以 \(2^k\)
>>	右移	8 >> 2 = 2	相当于除以 \(2^k\)（向下取整）

常用位运算技巧

1. 判断奇偶：n & 1 等于 1 则为奇数，等于 0 则为偶数。比 n % 2 更快。

2. 交换两个数（不用临时变量）：

a ^= b
b ^= a
a ^= b  # 交换完毕

3. 获取最低位的 1（Lowest Set Bit）：n & (-n)。例如 12 (1100) 的最低位1是 4 (0100)。这在树状数组（Binary Indexed Tree）中非常常用。

4. 消除最低位的 1：n & (n - 1)。例如 12 (1100) 变为 8 (1000)。可用于统计二进制中 1 的个数：

def count_bits(n):
    count = 0
    while n:
        n &= n - 1   # 每次消除最低位的 1
        count += 1
    return count

5. 判断是否为 2 的幂：n > 0 and (n & (n - 1)) == 0。2 的幂的二进制只有一个 1。

6. 用异或找唯一出现一次的数：如果一个数组中所有数字都出现两次，只有一个出现一次，那么将所有数字异或起来，结果就是那个唯一的数。因为 \(a \oplus a = 0\)，\(a \oplus 0 = a\)。

def single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

7. 位掩码（Bitmask） 常用于集合的子集枚举和状态压缩DP：

# 枚举集合 {0, 1, ..., n-1} 的所有子集
n = 3
for mask in range(1 << n):  # 0 到 2^n - 1
    subset = [i for i in range(n) if mask & (1 << i)]
    print(subset)

基本数学运算

本节介绍算法中常见的基本数学运算方法。

最大公约数（GCD）

辗转相除法（Euclidean Algorithm） 是求两个正整数最大公约数的经典算法，基于以下性质：

\[ \gcd(a, b) = \gcd(b, a \mod b) \]

当 \(b = 0\) 时，\(\gcd(a, 0) = a\)。

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Python 内置：math.gcd(a, b)

时间复杂度：\(O(\log(\min(a, b)))\)。

最小公倍数（LCM） 可以通过 GCD 求得：

\[ \text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)} \]

模运算（Modular Arithmetic）

在算法竞赛和大数运算中，经常需要对结果取模以防止溢出。常见的模数为 \(10^9 + 7\)。模运算的基本性质：

• \((a + b) \mod m = ((a \mod m) + (b \mod m)) \mod m\)
• \((a \times b) \mod m = ((a \mod m) \times (b \mod m)) \mod m\)
• \((a - b) \mod m = ((a \mod m) - (b \mod m) + m) \mod m\)（加 \(m\) 保证非负）

注意：除法不能直接取模，需要用模逆元（Modular Inverse）。当 \(m\) 为质数时，根据费马小定理：

\[ a^{-1} \equiv a^{m-2} \pmod{m} \]

快速幂（Fast Exponentiation）

快速幂利用指数的二进制分解，将 \(a^n\) 的计算从 \(O(n)\) 优化到 \(O(\log n)\)。核心思想：

\[ a^n = \begin{cases} 1 & \text{if } n = 0 \\ (a^{n/2})^2 & \text{if } n \text{ 为偶数} \\ a \cdot (a^{(n-1)/2})^2 & \text{if } n \text{ 为奇数} \end{cases} \]

def fast_pow(a, n, mod=None):
    result = 1
    while n > 0:
        if n & 1:               # n 为奇数
            result = result * a
            if mod:
                result %= mod
        a = a * a               # 底数平方
        if mod:
            a %= mod
        n >>= 1                 # n 右移一位（相当于 n //= 2）
    return result

# Python 内置：pow(a, n, mod) 即为快速幂取模

时间复杂度：\(O(\log n)\)。

快速幂配合模运算，可以高效计算模逆元：pow(a, m-2, m)（\(m\) 为质数时）。

素数判断与筛法

朴素判断：判断 \(n\) 是否为素数，只需检查 \(2\) 到 \(\sqrt{n}\) 是否有因子，时间复杂度 \(O(\sqrt{n})\)。

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

埃拉托斯特尼筛法（Sieve of Eratosthenes）：预处理求出 \([2, n]\) 范围内的所有素数，时间复杂度 \(O(n \log \log n)\)，空间复杂度 \(O(n)\)。

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):  # 从 i^2 开始标记
                is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

---

评论