【算法】【《计算机算法设计与分析（第5版）》笔记】第二章：递归与分治策略

文章目录

• • @[toc]
  • • 前导
    • • 【算法】【《计算机算法设计与分析（第5版）》笔记】第一章：算法概述
    • 2.1|递归的概念
    • • $Fibonacci$数列非递归定义
      • $Ackerman$函数
      • • 递归方程
        • `Python`实现
      • 排列问题
      • • 问题描述
        • 分治算法
        • `Python`实现
      • 整数划分问题
      • • 问题描述
        • 分治算法
        • `Python`实现
      • `Hanoi`塔问题
      • • 问题描述
        • `Python`实现
    • 2.2|分治法的基本思想
    • • 分治法时间复杂性
    • 2.3|二分搜索技术
    • • 问题描述
      • `Python`实现
      • 时间复杂性
    • 2.4|大整数的乘法
    • • 问题描述
      • 基础算法
      • • 时间复杂性
      • 优化算法
      • • 时间复杂性
      • `Python`实现
    • 2.5|`Strassen`矩阵乘法
    • • 问题描述
      • 基础算法
      • • 时间复杂性
      • `Strassen`算法
      • • 时间复杂性
      • 问题时间复杂性
      • `Python`实现
    • 2.6|棋盘覆盖
    • • 问题描述
      • 分治算法
      • 时间复杂性
      • `Python`实现
    • 2.7|合并排序
    • • 递归算法
      • • `Python`实现
        • 时间复杂性
      • 非递归算法
      • • `Python`实现
      • 自然合并排序
    • 2.8|快速排序
    • • `Python`实现
      • 时间复杂性
      • • 最坏时间复杂性
        • 最好时间复杂性
        • 平均时间复杂性
    • 2.9|线性时间选择
    • • 问题描述
      • 随机选择算法
      • • `Python`实现
        • 时间复杂性
      • $BFPRT$算法
      • • 时间复杂性
        • `Python`实现
    • 2.10|最接近点对问题
    • • 问题描述
      • 一维最接近点对算法
      • • `Python`实现
      • 二维最接近点对算法
      • • 分治算法
        • 时间复杂性
        • `Python`实现
    • 2.11|循环赛日程表
    • • 问题描述
      • 分治算法
      • • 示例
        • `Python`实现
      • 无运动员数量约束循环赛日程表算法
      • • 示例
        • `Python`实现

前导

【算法】【《计算机算法设计与分析（第5版）》笔记】第一章：算法概述

---

2.1|递归的概念

$Fibonacci$数列非递归定义

$$F(n)=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^{n+1}?{\left(\frac{1?\sqrt{5}}{2}\right)}^{n+1}\right]$$

$Ackerman$函数

• 并非一切递归函数都能用非递归方式定义
• $Ackerman$函数是一个双递归函数，当一个函数及它的一个变量由函数自身定义时，称这个函数是双递归函数

递归方程

$$A(n,m)=?\begin{array}{ll}2& n=1,m=0\\ 1& n=0,m\ge 0\\ n+2& n\ge 2,m=0\\ A(A(n?1,m),m?1)& n,m\ge 1\end{array}$$

• $A(n,m)$的自变量$m$的每个值都定义了一个单变量函数
  • 当$m=0$时，定义了函数“加$2$”
  • 当$m=1$时，由于$A(1,1)=A(A(0,1),0)=A(1,0)=2$，以及$A(n,1)=A(A(n?1,1),0)=A(n?1,1)+2(n>1)$，因此$A(n,1)=2n(n\ge 1)$，即$A(n,1)$是函数“乘$2$”
  • 当$m=2$时，$A(n,2)=A(A(n?1,2),1)=2A(n?1,2)$，$A(1,2)=A(A(0,2),1)=A(1,1)=2$，故$A(n,2)=2^n$
  • 类似地可以推出$A(n,3)=2^{2^{{╱}^2}}$，其中$2$的层数为$n$
  • $A(n,4)$的增长速度非常快，以至于没有适当的数学式子来表示这一函数
• 单变量的$Ackerman$函数$A(n)$定义为$A(n)=A(n,n)$，其拟逆函数 α ( n ) = min ? { ? k ∣ A ( k ) ≥ n ? } \alpha(n) = \min\set{k \mid A(k) \geq n} α(n)=min{k∣A(k)≥n}
  • $A(4)=2^{2^{{╱}^2}}$（其中$2$的层数为$65536$）的值非常大，如果要写出这个数将需要$\log (A(4))$位，即$2^{2^{{╱}^2}}$（$65535$层$2$的方幂）位，所以对于通常见到的正整数$n$，有$\alpha (n)\le 4$
  • 在理论上$\alpha (n)$没有上界

Python实现

def ackerman(n, m):
    if n == 1 and m == 0:
        return 2
    elif n == 0 and m >= 0:
        return 1
    elif n >= 2 and m == 0:
        return n + 2
    elif n >= 1 and m >= 1:
        return ackerman(ackerman(n - 1, m), m - 1)


res = ackerman(3, 3)

print(res)

排列问题

问题描述

• 设 R = { ? r 1 , r 2 , ? ? , r n ? } R = \set{r_{1} , r_{2} , \cdots , r_{n}} R={r1?,r2?,?,rn?}是要进行排列的$n$个元素， R i = R ? { ? r i ? } R_{i} = R - \set{r_{i}} Ri?=R?{ri?}

分治算法

• 集合$X$中的元素的全排列记为$Perm(X)$，$(r_i)Perm(X)$表示在全排列$Perm(X)$的每个排列前加上前缀$r_i$得到的排列

• $R$的全排列可递归定义为

  • 当$n=1$时，$Perm(R)=(r)$，其中$r$是集合$R$中唯一的元素

  • 当$n>1$时，$Perm(R)$由$(r_1)Perm(R_1)$，$(r_2)Perm(R_2)$，$?$，$(r_n)Perm(R_n)$构成

• 递归地产生所有前缀是num[0:k - 1]，且后缀是num[k:m]的全排列的所有排列

Python实现

def permute(nums):
    if len(nums) <= 1:
        return [nums]

    result = []

    for i in range(len(nums)):
        m = nums[i]
        remaining_nums = nums[:i] + nums[i + 1:]

        sub_permutations = permute(remaining_nums)

        for p in sub_permutations:
            result.append([m] + p)

    return result


nums = [1, 2, 3]

permutations = permute(nums)

for p in permutations:
    print(p)

整数划分问题

问题描述

• 将正整数$n$表示成一系列正整数之和，$n=n_1+n_2+?+n_k(n_1\ge n_2\ge ?\ge n_k\ge 1,k\ge 1)$
• 正整数$n$的这种表示称为正整数$n$的划分，正整数$n$的不同的划分个数称为正整数$n$的划分数，记为$p(n)$

分治算法

• 在正整数$n$的所有划分中，将最大加数$n_1$不大于$m$的划分个数记作$q(n,m)$，可以建立$q(n,m)$的递归关系

$$q(n,m)=?\begin{array}{ll}1,& n=1,m=1\\ q(n,n),& n<m\\ 1+q(n,n?1),& n=m\\ q(n,m?1)+q(n?m,m),& n>m>1\end{array}$$

Python实现

def integer_partition(n, m):
    if n < 1 or m < 1:
        return 0

    if n == 1 or m == 1:
        return 1

    if n < m:
        return integer_partition(n, n)

    if n == m:
        return integer_partition(n, m - 1) + 1

    return integer_partition(n, m - 1) + integer_partition(n - m, m)


n = 6

res = integer_partition(n, n)

print(f'The number of partitions for {n} is: {res}')

Hanoi塔问题

问题描述

• 设$a$、$b$、$c$是三个塔座，开始时，在塔座$a$上有一叠共$n$个圆盘，这些圆盘自下而上，由大到小地叠放在一起，各圆盘从小到大编号为$1$，$2$，$?$，$n$，要求将塔座$a$上的这一叠圆盘移到塔座$b$上，并仍按照同样顺序叠置
• 在移动圆盘时应遵守以下移动规则
  • 每次只能移动一个圆盘
  • 任何时刻都不允许将较大的圆盘压在较小的圆盘之上

Python实现

def hanoi(n, source, target, auxiliary):
    if n > 0:
        # 将 n - 1 个盘子从源柱移动到辅助柱
        hanoi(n - 1, source, auxiliary, target)
        # 将第 n 个盘子从源柱移动到目标柱
        print(f'将盘子 {n} 从 {source} 移动到 {target}')
        # 将 n - 1 个盘子从辅助柱移动到目标柱
        hanoi(n - 1, auxiliary, target, source)


n = 3

hanoi(n, 'A', 'B', 'C')

---

2.2|分治法的基本思想

分治法时间复杂性

• $k$为子问题的个数，$n/m$为子问题的规模

$$T(n)=\{\begin{array}{ll}O(1)& n=1\\ kT(n/m)+f(n)& n>1\end{array}$$

$$T(n)=n^{{\log }_{m}k}+\sum _{j=0}^{{\log }_{m}n?1}{k}^{j}f(n/m^j)$$

---

2.3|二分搜索技术

问题描述

• 给定已排好序的$n$个元素a[0:n - 1]，在这$n$个元素中找出一特定元素$x$

Python实现

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1


arr = [1, 3, 5, 7, 9]
target = 5

res = binary_search(arr, target)

if res != -1:
    print(f'目标元素 {target} 在数组中的索引为 {res}')
else:
    print('目标元素不在数组中')

时间复杂性

• 在最坏情况下，while循环被执行了$O(\log n)$次，循环体内运算需要$O(1)$时间，因此整个算法在最坏情况下的时间复杂性为$O(\log n)$

---

2.4|大整数的乘法

问题描述

• 设$X$和$Y$都是$n$位二进制整数，计算它们的乘积$XY$

基础算法

• 将$n$位二进制整数$X$和$Y$都分为$2$段，每段的长为$n/2$位（假设$n$是$2$的幂）
  • $X=A\times 2^{n/2}+B$
  • $Y=C\times 2^{n/2}+D$
  • $XY=(A\times 2^{n/2}+B)(C\times 2^{n/2}+D)=AC\times 2^n+(AD+BC)\times 2^{n/2}+BD$

时间复杂性

• 如果按此式计算$XY$，必须进行$4$次$n/2$位整数的乘法，$3$次不超过$2n$位的整数加法，以及$2$次移位，所有这些加法和移位共用$O(n)$步运算

$$T(n)=\{\begin{array}{ll}O(1)& n=1\\ 4T(n/2)+O(n)& n>1\end{array}$$

$$T(n)=O(n^2)$$

优化算法

• 要想改进算法的计算复杂性，必须减少乘法次数，把$XY$写成另一种形式
  • $XY=AC\times 2^n+((A?B)(D?C)+AC+BD)\times 2^{n/2}+BD$

时间复杂性

• 需做$3$次$n/2$位整数的乘法，$6$次加减法和$2$次移位

$$T(n)=\{\begin{array}{ll}O(1)& n=1\\ 3T(n/2)+O(n)& n>1\end{array}$$

$$T(n)=O(n^{\log 3})=O(n^{1.59})$$

Python实现

def karatsuba_multiply(x, y):
    # 如果乘数之一为 0, 则直接返回 0
    if x == 0 or y == 0:
        return 0

    # 将乘数转换为字符串, 并获取它们的位数
    x_str = str(x)
    y_str = str(y)

    n = max(len(x_str), len(y_str))

    # 达到基本情况时, 使用传统的乘法
    if n == 1:
        return x * y

    # 将乘数补齐到相同的位数
    x_str = x_str.zfill(n)
    y_str = y_str.zfill(n)

    # 将乘数划分为两部分
    m = n // 2

    high1, low1 = int(x_str[:m]), int(x_str[m:])
    high2, low2 = int(y_str[:m]), int(y_str[m:])

    # 递归地计算三个乘法
    z0 = karatsuba_multiply(low1, low2)
    z1 = karatsuba_multiply((low1 + high1), (low2 + high2))
    z2 = karatsuba_multiply(high1, high2)

    # 计算结果
    res = (z2 * 10 ** (2 * m)) + ((z1 - z2 - z0) * 10 ** m) + z0

    return res


x = 123456789012345678901234567890
y = 987654321098765432109876543210

res = karatsuba_multiply(x, y)

print(f'{x} * {y} = {res}')

---

2.5|Strassen矩阵乘法

问题描述

• 设$A$和$B$是两个$n\times n$矩阵，$A$和$B$的乘积矩阵$C$中元素$c_{ij}=\sum _{k=1}^n{a}_{ik}{b}_{kj}$
• 每计算$C$的一个元素$c_{ij}$，需要做$n$次乘法和$n?1$次加法，求出矩阵$C$的$n^2$个元素所需的时间为$O(n^3)$

基础算法

• 假设$n$是$2$的幂，将矩阵$A$、$B$和$C$中每个矩阵都分块成$4$个大小相等的子矩阵，每个子矩阵都是$n/2\times n/2$的方阵

$$\left|\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right|=\left|\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right|\left|\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right|$$

$$\begin{gathered} C_{11}=A_{11}{B}_{11}+A_{12}{B}_{21} \\ {C}_{12}=A_{11}{B}_{12}+A_{12}{B}_{22} \\ {C}_{21}=A_{21}{B}_{11}+A_{22}{B}_{21} \\ {C}_{22}=A_{21}{B}_{12}+A_{22}{B}_{22} \end{gathered}$$

时间复杂性

• 计算$2$个$n$阶方阵的乘积转化为计算$8$个$n/2$阶方阵的乘积和$4$个$n/2$阶方阵的加法，$2$个$n/2\times n/2$矩阵的加法显然可以在$O(n^2)$时间内完成

$$T(n)=\{\begin{array}{ll}O(1)& n=2\\ 8T(n/2)+O(n^2)& n>2\end{array}$$

$$T(n)=O(n^3)$$

Strassen算法

• Strassen算法只用了$7$次乘法运算，但增加了加减法的运算次数

$$\begin{gathered} M_1=A_{11}(B_{12}?B_{22}) \\ {M}_2=(A_{11}+A_{12})B_{22} \\ {M}_3=(A_{21}+A_{22})B_{11} \\ {M}_4=A_{22}(B_{21}?B_{11}) \\ {M}_5=(A_{11}+A_{22})(B_{11}+B_{22}) \\ {M}_6=(A_{12}?A_{22})(B_{21}+B_{22}) \\ {M}_7=(A_{11}?A_{21})(B_{11}+B_{12}) \end{gathered}$$

$$\begin{gathered} C_{11}=M_5+M_4?M_2+M_6 \\ {C}_{12}=M_1+M_2 \\ {C}_{21}=M_3+M_4 \\ {C}_{22}=M_5+M_1?M_3?M_7 \end{gathered}$$

时间复杂性

• Strassen算法用了$7$次对于$n/2$阶矩阵乘积的递归调用和$18$次$n/2$阶矩阵的加减运算

$$T(n)=\{\begin{array}{ll}O(1)& n=2\\ 7T(n/2)+O(n^2)& n>2\end{array}$$

$$T(n)=O(n^{\log 7})\approx O(n^{2.81})$$

问题时间复杂性

• $Hopcroft$和$Kerr$已经证明计算$2$个$2\times 2$矩阵的乘积，$7$次乘法是必要的
• 目前最好的计算时间上界是$O(n^{2.376})$，所知的矩阵乘法的最好下界仍是它的平凡下界$\Omega (n^2)$

Python实现

import numpy as np


def strassen_matrix_multiply(a, b):
    n = a.shape[0]

    # 如果输入矩阵的维度小于等于阈值, 使用传统的矩阵乘法
    if n <= 128:
        return np.dot(a, b)

    # 将输入矩阵划分为四个子矩阵
    mid = n // 2

    a11 = a[:mid, :mid]
    a12 = a[:mid, mid:]
    a21 = a[mid:, :mid]
    a22 = a[mid:, mid:]

    b11 = b[:mid, :mid]
    b12 = b[:mid, mid:]
    b21 = b[mid:, :mid]
    b22 = b[mid:, mid:]

    # 递归地计算七个矩阵乘法
    m1 = strassen_matrix_multiply(a11, b12 - b22)
    m2 = strassen_matrix_multiply(a11 + a12, b22)
    m3 = strassen_matrix_multiply(a21 + a22, b11)
    m4 = strassen_matrix_multiply(a22, b21 - b11)
    m5 = strassen_matrix_multiply(a11 + a22, b11 + b22)
    m6 = strassen_matrix_multiply(a12 - a22, b21 + b22)
    m7 = strassen_matrix_multiply(a11 - a21, b11 + b12)

    # 计算结果矩阵的四个子矩阵
    c11 = m5 + m4 - m2 + m6
    c12 = m1 + m2
    c21 = m3 + m4
    c22 = m5 + m1 - m3 - m7

    # 组合四个子矩阵形成结果矩阵
    c = np.zeros((n, n))

    c[:mid, :mid] = c11
    c[:mid, mid:] = c12
    c[mid:, :mid] = c21
    c[mid:, mid:] = c22

    return c


a = np.random.randint(0, 10, (4, 4))
b = np.random.randint(0, 10, (4, 4))

res = strassen_matrix_multiply(a, b)

print('矩阵a:')
print(a)

print('\n矩阵b:')
print(b)

print('\n乘积矩阵:')
print(res)

---

2.6|棋盘覆盖

问题描述

• 在一个$2^k\times 2^k$个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘
• 用$4$种不同形态的$L$型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格，且任何$2$个$L$型骨牌不得重复覆盖

分治算法

• 当$k>0$时，将$2^k\times 2^k$棋盘分割为$4$个$2^{k?1}\times 2^{k?1}$子棋盘，特殊方格必位于$4$个较小子棋盘之一中，其余$3$个子棋盘中无特殊方格
• 为了将这$3$个无特殊方格的子棋盘转化为特殊棋盘，可以用一个$L$型骨牌覆盖这$3$个较小棋盘的会合处

时间复杂性

$$T(k)=\{\begin{array}{ll}O(1)& k=0\\ 4T(k?1)+O(1)& k>0\end{array}$$

$$T(k)=O(4^k)$$

• 由于覆盖一个$2^k\times 2^k$棋盘所需的$L$型骨牌个数为$(4^k?1)/3$，故算法是一个在渐进意义下最优的算法

Python实现

def chessboard_cover(board, tr, tc, dr, dc, size):
    """
    :param board: 棋盘
    :param tr: 棋盘左上角行号
    :param tc: 棋盘左上角列号
    :param dr: 特殊方格行号
    :param dc: 特殊方格列号
    :param size: 棋盘大小
    """
    global tile_count

    # 基本情况: 棋盘大小为 1, 直接放置骨牌
    if size == 1:
        return

    t = tile_count
    tile_count += 1

    # 将棋盘分成 4 个子棋盘
    s = size // 2

    # 左上子棋盘
    if dr < tr + s and dc < tc + s:
        chessboard_cover(board, tr, tc, dr, dc, s)
    else:
        board[tr + s - 1][tc + s - 1] = t
        chessboard_cover(board, tr, tc, tr + s - 1, tc + s - 1, s)

    # 右上子棋盘
    if dr < tr + s and dc >= tc + s:
        chessboard_cover(board, tr, tc + s, dr, dc, s)
    else:
        board[tr + s - 1][tc + s] = t
        chessboard_cover(board, tr, tc + s, tr + s - 1, tc + s, s)

    # 左下子棋盘
    if dr >= tr + s and dc < tc + s:
        chessboard_cover(board, tr + s, tc, dr, dc, s)
    else:
        board[tr + s][tc + s - 1] = t
        chessboard_cover(board, tr + s, tc, tr + s, tc + s - 1, s)

    # 右下子棋盘
    if dr >= tr + s and dc >= tc + s:
        chessboard_cover(board, tr + s, tc + s, dr, dc, s)
    else:
        board[tr + s][tc + s] = t
        chessboard_cover(board, tr + s, tc + s, tr + s, tc + s, s)


size = 8
board = [[0] * size for _ in range(size)]

special_row = 3
special_col = 4

board[special_row][special_col] = -1

tile_count = 0

chessboard_cover(board, 0, 0, special_row, special_col, size)

for row in board:
    print(row)

---

2.7|合并排序

递归算法

Python实现

def merge_sort(arr):
    # 基本情况: 当数组长度为 1 或 0 时, 直接返回
    if len(arr) <= 1:
        return arr

    # 将数组分成两半
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # 递归地对左右两半进行排序
    left_sorted = merge_sort(left)
    right_sorted = merge_sort(right)

    # 合并已排序的左右两半
    merged = merge(left_sorted, right_sorted)

    return merged


def merge(left_sorted, right_sorted):
    merged = []
    i = j = 0

    # 比较左右两个数组的元素, 按顺序合并到结果数组中
    while i < len(left_sorted) and j < len(right_sorted):
        if left_sorted[i] <= right_sorted[j]:
            merged.append(left_sorted[i])
            i += 1
        else:
            merged.append(right_sorted[j])
            j += 1

    # 将剩余的元素添加到结果数组中
    while i < len(left_sorted):
        merged.append(left_sorted[i])
        i += 1

    while j < len(right_sorted):
        merged.append(right_sorted[j])
        j += 1

    return merged


arr = [5, 3, 8, 4, 2, 1, 6, 7]

sorted_arr = merge_sort(arr)

print(f'sorted_arr:', sorted_arr)

时间复杂性

$$T(n)=\{\begin{array}{ll}O(1)& n\le 1\\ 2T(n/2)+O(n)& n>1\end{array}$$

$$T(n)=O(n\log n)$$

• 由于排序问题的计算时间下界为$\Omega (n\log n)$，故合并排序算法是一个渐进最优算法

非递归算法

Python实现

def merge_sort(arr):
    # 将列表中的每个元素转换为单个元素的子列表
    sublists = [[val] for val in arr]

    # 依次合并相邻的子列表, 直到只剩下一个排序好的列表
    while len(sublists) > 1:
        merged_sublists = []

        # 两两合并相邻的子列表
        for i in range(0, len(sublists), 2):
            sublist_1 = sublists[i]
            sublist_2 = sublists[i + 1] if i + 1 < len(sublists) else []

            merged = merge(sublist_1, sublist_2)
            merged_sublists.append(merged)

        sublists = merged_sublists

    # 返回最终的排序结果
    return sublists[0] if sublists else []


def merge(left_sorted, right_sorted):
    merged = []
    i = j = 0

    # 比较左右两个列表的元素, 按顺序合并到结果列表中
    while i < len(left_sorted) and j < len(right_sorted):
        if left_sorted[i] <= right_sorted[j]:
            merged.append(left_sorted[i])
            i += 1
        else:
            merged.append(right_sorted[j])
            j += 1

    # 将剩余的元素添加到结果列表中
    while i < len(left_sorted):
        merged.append(left_sorted[i])
        i += 1

    while j < len(right_sorted):
        merged.append(right_sorted[j])
        j += 1

    return merged


arr = [5, 3, 8, 4, 2, 1, 6, 7]

sorted_arr = merge_sort(arr)

print(f'sorted_arr:', sorted_arr)

自然合并排序

• 用$1$次对数组的线性扫描找出所有排好序的子数组段，然后将相邻的排好序的子数组段两两合并，构成更大的排好序的子数组段

---

2.8|快速排序

Python实现

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]

    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]

    return quick_sort(less) + [pivot] + quick_sort(greater)


arr = [3, 1, 5, 2, 4]

sorted_arr = quick_sort(arr)

print(f'sorted_arr', sorted_arr)

时间复杂性

• 快速排序的运行时间与划分是否对称有关，其最坏情况发生在划分过程产生的两个区域分别包含$n?1$个元素和$1$个元素的时候，在最好情况下，每次划分所取的基准都恰好为中值，即每次划分都产生两个大小为$n/2$的区域

最坏时间复杂性

$$T(n)=\{\begin{array}{ll}O(1)& n\le 1\\ T(n?1)+O(n)& n>1\end{array}$$

$$T(n)=n^2$$

最好时间复杂性

$$T(n)=\{\begin{array}{ll}O(1)& n\le 1\\ 2T(n/2)+O(n)& n>1\end{array}$$

$$T(n)=O(n\log n)$$

平均时间复杂性

• 可以证明，快速排序算法在平均情况下的时间复杂性也是$O(n\log n)$

---

2.9|线性时间选择

问题描述

• 给定线性序集中$n$个元素和一个整数$k(1\le k\le n)$，找出这$n$个元素中第$k$小的元素

随机选择算法

Python实现

import random


def partition(nums, low, high):
    pivot_index = random.randint(low, high)
    pivot = nums[pivot_index]

    # 将pivot元素移动到列表的最右边
    nums[pivot_index], nums[high] = nums[high], nums[pivot_index]

    # 通过交换操作, 将小于 pivot 的元素移动到左边, 大于 pivot 的元素移动到右边
    i = low
    for j in range(low, high):
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1

    # 将 pivot 元素放置到正确的位置
    nums[i], nums[high] = nums[high], nums[i]

    return i


def quick_select(nums, low, high, k):
    if low == high:
        return nums[low]

    # 划分数组, 并获取 pivot 元素的索引
    pivot_index = partition(nums, low, high)

    j = pivot_index - low + 1
    # 如果 pivot 元素的索引等于 k, 则返回该元素
    if j == k:
        return nums[pivot_index]

    # 如果 pivot 元素的索引大于 k, 则在左侧继续查找
    elif j > k:
        return quick_select(nums, low, pivot_index - 1, k)

    # 如果 pivot 元素的索引小于 k, 则在右侧继续查找
    else:
        return quick_select(nums, pivot_index + 1, high, k - j)


def find_kth_smallest(nums, k):
    if k < 1 or k > len(nums):
        raise ValueError('Invalid value of k')

    return quick_select(nums, 0, len(nums) - 1, k)


nums = [3, 1, 5, 2, 4]
k = 2

res = find_kth_smallest(nums, k)

print(f'第 {k} 小的元素为 {res}')

时间复杂性

• 随机选择算法在最坏情况下需要$\Omega (n^2)$时间，平均情况下需要$O(n)$时间

$BFPRT$算法

• 如果能在线性时间内找到一个划分基准，使得按这个基准划分出的两个子数组的长度都至少为原数组长度的$\epsilon$倍（$0<\epsilon <1$是某个常数），那么在最坏情况下用$O(n)$时间就可以完成选择任务

  • 例如，若$\epsilon =9/10$，算法递归调用所产生的子数组的长度至少缩短$1/10$，所以在最坏情况下，算法所需的计算时间$T(n)$满足递归式$T(n)\le T(9n/10)+O(n)$，由此可得$T(n)=O(n)$

• 将$n$个输入元素划分成$?n/5?$个组，每组$5$个元素（除可能有一个组不是$5$个元素外），用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共$?n/5?$个

• 递归调用找出这$?n/5?$个元素的中位数，如果$?n/5?$是偶数，就找它的两个中位数中较大的一个，然后以这个元素作为划分基准

• 设所有元素互不相同，找出的基准$x$至少比$3?(n?5)/10?$个元素大，至少比$3?(n?5)/10?$个元素小，当$n\ge 75$时，$3?(n?5)/10?\ge n/4$，所以按此基准划分所得的两个子数组的长度都至少缩短$1/4$

时间复杂性

• 设对$n$个元素的数组调用算法需要$T(n)$时间
• 找中位数$x$最多用$T(n/5)$时间
• 按照算法所选的基准$x$进行划分所得的两个子数组分别最多有$3n/4$个元素，无论对哪一个子数组调用算法都最多用$T(3n/4)$时间

$$T(n)\le \{\begin{array}{ll}{C}_1,& n<75\\ C_{2}n+T(n/5)+T(3n/4),& n\ge 75\end{array}$$

$$T(n)=O(n)$$

Python实现

import statistics


def find_median_of_medians(arr):
    # 将数组划分为大小为 5 的子数组
    subarrays = [arr[i:i + 5] for i in range(0, len(arr), 5)]

    # 计算每个子数组的中位数
    medians = [statistics.median(subarray) for subarray in subarrays]

    # 如果元素数量小于等于 5, 直接返回中位数
    if len(medians) <= 5:
        return statistics.median(medians)

    # 递归调用中位数的中位数算法
    return find_median_of_medians(medians)


def linear_time_select(arr, k):
    # 找到中位数的中位数
    median_of_medians = find_median_of_medians(arr)

    # 将数组划分为三个部分
    less = [x for x in arr if x < median_of_medians]
    equal = [x for x in arr if x == median_of_medians]
    greater = [x for x in arr if x > median_of_medians]

    # 根据划分后的数组长度选择下一步操作
    if k <= len(less):
        # 在较小的部分递归查找第 k 小元素
        return linear_time_select(less, k)
    elif k <= len(less) + len(equal):
        # 第 k 小元素等于中位数的中位数
        return median_of_medians
    else:
        # 在较大的部分递归查找第 k 小元素
        return linear_time_select(greater, k - len(less) - len(equal))


arr = [3, 1, 5, 2, 4, 9, 7, 8, 6]
k = 5

res = linear_time_select(arr, k)

print(f'第 {k} 小的元素为 {res}')

---

2.10|最接近点对问题

问题描述

• 给定平面上$n$个点，找其中的一对点，使得在$n$个点组成的所有点对中，该点对的距离最小

一维最接近点对算法

Python实现

import sys


def closest_pair(points):
    points.sort()  # 按照横坐标排序
    min_dist = sys.maxsize  # 初始化最小距离为一个很大的数
    closest = None  # 初始化最接近点对为 None

    for i in range(len(points) - 1):
        dist = abs(points[i] - points[i + 1])  # 计算相邻点对的距离

        if dist < min_dist:
            min_dist = dist
            closest = (points[i], points[i + 1])

    return closest


points = [2, 4, 1, 5, 8, 9, 3]

res = closest_pair(points)

print(f'最接近的点对: {res}')

二维最接近点对算法

分治算法

• 选取一垂直线$l:x=m$，$m$为$S$中各点$x$坐标的中位数，将$S$分割为 S 1 = { ? p ∈ S ∣ x ( p ) ≤ m ? } S_{1} = \set{p \in S \mid x(p) \leq m} S1?={p∈S∣x(p)≤m}和 S 2 = { ? p ∈ S ∣ x ( p ) > m ? } S_{2} = \set{p \in S \mid x(p) > m} S2?={p∈S∣x(p)>m}
• 递归地在$S_1$和$S_2$上解最接近点对问题，分别得到$S_1$和$S_2$中的最小距离$d_1$和$d_2$
• 设 d = min ? { ? d 1 , d 2 ? } d = \min\set{d_{1} , d_{2}} d=min{d1?,d2?}，若$S$的最接近点对$(p,q)$之间的距离小于$d$，则$p$和$q$必分属于$S_1$和$S_2$，设$p\in S_1$，$q\in S_2$，则$p$和$q$距直线$l$的距离均小于$d$
• $P_1$和$P_2$分别表示直线$l$的左侧和右侧宽为$d$的两个垂直长条区域，则$p\in P_1$且$q\in P_2$，此时$P_1$中所有点与$P_2$中所有点构成的点对均为最接近点对的候选者，在最坏情况下有$n^2/4$对这样的候选者，但是对于$P_1$中任一点$p$，$P_2$中最多只有$6$个点与它构成最接近点对的候选者
  • 实际上对于$P_1$中任一点$p$，若与$P_2$中的点构成最接近点对的候选者，则必有$distance(p,q)<d$，满足这个条件的$P_2$中的点一定落在一个$d\times 2d$的矩形$R$中
  • 可将矩形$R$的长为$2d$的边$3$等分，将长为$d$的边$2$等分，由此导出$6$个$(d/2)\times (2d/3)$的矩形，矩形$R$中最多只有$6$个$S$中的点

• 合并步骤中，最多只需检查$6\times n/2=3n$个候选者，为了确切地知道要检查哪$6$个点，将$p$和$P_2$中的点投影到垂直线$l$上，能与$p$点一起构成最接近点对候选者的$q$与$p$在$l$上投影点的距离小于$d$，且这种投影点最多只有$6$个，若将$P_1$和$P_2$中所有$S$中点按其$y$坐标排好序，则对$P_1$中所有点，对排好序的点列做一次扫描，就可以找出所有最接近点对的候选者

时间复杂性

$$T(n)=\{\begin{array}{ll}O(1),& n<4\\ 2T(n/2)+O(n),& n\ge 4\end{array}$$

$$T(n)=O(n\log n)$$

Python实现

import math


# 计算两点之间的欧几里德距离
def dist(p1, p2):
    return math.sqrt((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2)


# 分治法求解最接近点对问题
def closest_pair(points):
    # 如果点集中的点个数小于等于 3 个, 直接计算并返回最小距离对
    if len(points) <= 3:
        min_dist = float('inf')
        min_pair = None

        for i in range(len(points)):
            for j in range(i + 1, len(points)):
                d = dist(points[i], points[j])

                if d < min_dist:
                    min_dist = d
                    min_pair = (points[i], points[j])

        return min_pair

    # 将点集按照 x 坐标排序
    sorted_points = sorted(points, key=lambda p: p[0])

    # 将点集分成左右两部分
    mid = len(sorted_points) // 2

    left_points = sorted_points[:mid]
    right_points = sorted_points[mid:]

    # 递归求解左右两部分的最接近点对
    left_min_pair = closest_pair(left_points)
    right_min_pair = closest_pair(right_points)

    # 取左右两部分最接近点对的最小距离
    if left_min_pair is None:
        min_dist = dist(right_min_pair[0], right_min_pair[1])
        min_pair = right_min_pair
    elif right_min_pair is None:
        min_dist = dist(left_min_pair[0], left_min_pair[1])
        min_pair = left_min_pair
    else:
        left_dist = dist(left_min_pair[0], left_min_pair[1])
        right_dist = dist(right_min_pair[0], right_min_pair[1])

        if left_dist <= right_dist:
            min_dist = left_dist
            min_pair = left_min_pair
        else:
            min_dist = right_dist
            min_pair = right_min_pair

    # 在横跨左右两部分的点中寻找更近的点对
    mid_x = sorted_points[mid][0]
    strip = []

    # 将点集按照 y 坐标排序
    sorted_points = sorted(points, key=lambda p: p[1])

    for point in sorted_points:
        if abs(point[0] - mid_x) < min_dist:
            strip.append(point)

    for i in range(len(strip)):
        for j in range(i + 1, min(i + 7, len(strip))):
            d = dist(strip[i], strip[j])

            if d < min_dist:
                min_dist = d
                min_pair = (strip[i], strip[j])

    return min_dist, min_pair


points = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]

min_dist, min_pair = closest_pair(points)

print(f'最接近的点对为: {min_pair}, 点对距离为 {min_dist}')

---

2.11|循环赛日程表

问题描述

• 设有$n=2^k$个运动员要进行网球循环赛，设计一个满足以下要求的比赛日程表
  • 每个选手必须与其他$n?1$个选手各赛一次
  • 每个选手一天只能赛一次
  • 循环赛一共进行$n?1$天

分治算法

• $n$个选手的比赛日程表可以通过$n/2$个选手的比赛日程表决定，递归调用，直到只剩下两个选手，比赛日程表的制定就变得简单了

示例

• $8$个选手的比赛日程表
• 先制定$2$个选手的比赛日程表，如下图所示

• 有了最基本情况后就可以逐层返回，得到$4$个选手的比赛日程表，如下图所示

• 最后得到$8$个选手的比赛日程表，如下图所示

• 其中第$1$列表示$8$个选手，第$i(2\le i\le 8)$列表示第$i?1$天每个选手的对手

Python实现

def generate_schedule(k):
    n = 1
    for i in range(1, k + 1):
        n *= 2

    schedule = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        schedule[1][i] = i

    m = 1
    for s in range(1, k + 1):
        n //= 2

        for t in range(1, n + 1):
            for i in range(m + 1, 2 * m + 1):
                for j in range(m + 1, 2 * m + 1):
                    schedule[i][j + (t - 1) * m * 2] = schedule[i - m][j + (t - 1) * m * 2 - m]
                    schedule[i][j + (t - 1) * m * 2 - m] = schedule[i - m][j + (t - 1) * m * 2]

        m *= 2

    return schedule


k = 3

schedule = generate_schedule(k)

for item in schedule:
    print(item)

无运动员数量约束循环赛日程表算法

• 如果队伍数为奇数，则添加一个虚拟队伍来凑成偶数
• 固定第一支队伍的位置，其他队伍按顺序循环移动

示例

• $5$个选手的比赛日程表

• 选手数为奇数，首先添加一个虚拟队伍$6$来凑成偶数，如下图所示

• 第$1$轮竞争队伍安排，其中与虚拟队伍$6$比赛即为轮空，如下图所示

• 固定队伍$1$的位置，其他队伍按顺序循环移动，得到第$2$轮竞争队伍安排，如下图所示

• 第$3$到$5$轮以此类推

Python实现

def generate_schedule(num_teams):
    # 如果队伍数为奇数, 添加一个虚拟队伍来凑成偶数
    if num_teams % 2 != 0:
        num_teams += 1

    num_rounds = num_teams - 1  # 总轮数
    half_teams = num_teams // 2  # 每轮比赛的队伍数

    teams = list(range(1, num_teams + 1))

    schedule = []
    for round in range(num_rounds):
        matches = []

        for i in range(half_teams):
            match = (teams[i], teams[num_teams - i - 1])
            matches.append(match)

        schedule.append(matches)

        # 重新排列队伍, 固定第一支队伍, 其他队伍按顺序循环移动
        teams.insert(1, teams.pop())

    return schedule


num_teams = 8

schedule = generate_schedule(num_teams)

round_num = 1
for matches in schedule:
    print(f'Round {round_num}:')

    for match in matches:
        print(f'Team {match[0]} vs Team {match[1]}')

    print()

    round_num += 1

---