首页algorithms

# 算法概述

# 算法的定义

算法是由若⼲条指令组成的有穷序列

# 算法的性质

输入、输出、确定性、有限性

# 程序与算法的区别

程序是算法用某种程序设计语言的具体实现
程序可以不满足算法的有限性

# 问题求解

图 0

# 算法复杂度

# 复杂性的计量

C=F(N,I,A)  ⟹  T=T(N,I),S=S(N,I)C = F(N,I,A) \implies T = T(N,I), S = S(N,I)

其中，NN 为问题规模，II 为问题的输入，AA 为算法，FF 为复杂性函数，TT 为时间复杂度，SS 为空间复杂度，CC 为复杂性

# 时间复杂度

T=T(N,I)=∑i=1ktiei(N,I)T = T(N,I) = \sum\limits_{i=1}^{k} t_i e_i(N,I)

其中，tit_i 为第 ii 条指令的执行时间（元运算时间），ei(N,I)e_i(N,I) 为第 ii 条指令的执行次数（元运算次数），kk 为算法的指令数（元运算种类）

不可能精确计算出 T(N,I)T(N,I)，只能估计

  • 最坏情况时间复杂度：Tmax⁡(N)=max⁡I∈DNT(N,I)=max⁡I∈DN∑i=1ktiei(N,I)=∑i=1ktiei(N,I∗)=T(N,I∗)T_{\max}(N) = \max\limits_{I \in D_N} T(N,I) = \max\limits_{I \in D_N} \sum\limits_{i=1}^{k} t_i e_i(N,I) = \sum\limits_{i=1}^{k} t_i e_i(N,I^\ast) = T(N, I^\ast)，其中 I∗I^\ast 为使得 T(N,I)T(N,I) 最大的输入
  • 最好情况时间复杂度：Tmin⁡(N)=min⁡I∈DNT(N,I)=∑i=1ktiei(N,I~)=T(N,I~)T_{\min}(N) = \min\limits_{I \in D_N} T(N,I) = \sum\limits_{i=1}^{k} t_i e_i(N,\tilde{I}) = T(N, \tilde{I})，其中 I~\tilde{I} 为使得 T(N,I)T(N,I) 最小的输入
  • 平均时间复杂度：Tavg(N)=∑I∈DNP(I)T(N,I)=∑I∈DNP(I)∑i=1ktiei(N,I)T_{\text{avg}}(N) = \sum\limits_{I \in D_N} P(I) T(N,I) = \sum\limits_{I \in D_N} P(I) \sum\limits_{i=1}^{k} t_i e_i(N,I)，其中 P(I)P(I) 为输入 II 出现的概率

可操作性最好且最有实际价值的是最坏情况下的复杂度

# 复杂性的渐进性态

# 渐进性态

设T(N)T(N) 为算法AA 的时间复杂度，则它是NN 的单增函数。如果存在一个函数T~(N)\tilde{T}(N)，使得对于N→∞N \rightarrow \infty，有T(N)−T~(N)T(N)→0\frac{T(N)-\tilde{T}(N)}{T(N)} \rightarrow 0，则称T~(N)\tilde{T}(N) 是T(N)T(N) 当N→∞N \rightarrow \infty 时的渐进性态（渐进复杂性）

# 渐进性态的阶

设f(N)f(N) 和g(N)g(N) 是定义在正整数集合上的正函数

# 大OO 表示法（上限）

如果存在正常数CC 和N0N_0，使得对于一切N>N0N>N_0，有f(N)≤Cg(N)f(N) \leq Cg(N)，则称f(N)f(N) 在N→∞N \rightarrow \infty 时有上界，且g(N)g(N) 是f(N)f(N) 的一个上界，记作f(N)=O(g(N))f(N) = O(g(N))

上界的阶越低，则评估越精确，结果就越有价值。

  1. O(f)+O(g)=O(max⁡(f,g))O(f) + O(g) = O(\max(f,g))
  2. O(f)+O(g)=O(f+g)O(f) + O(g) = O(f+g)
  3. O(f)⋅O(g)=O(f⋅g)O(f) \cdot O(g) = O(f \cdot g)
  4. 如果g(N)=O(f(N))g(N) = O(f(N))，则O(f)+O(g)=O(f)O(f) + O(g) = O(f)
  5. f=O(f)f = O(f)
  6. O(Cf(N))=O(f(N))O(Cf(N)) = O(f(N))

图 1

# 大Ω\Omega 表示法（下限）

如果存在正常数CC 和N0N_0，使得对于一切N>N0N>N_0，有f(N)≥Cg(N)f(N) \geq Cg(N)，则称f(N)f(N) 在N→∞N \rightarrow \infty 时有下界，且g(N)g(N) 是f(N)f(N) 的一个下界，记作f(N)=Ω(g(N))f(N) = \Omega(g(N))

下界的阶越高，则评估越精确，结果就越有价值。

# 大Θ\Theta 表示法

f(N)=Θ(g(N))f(N) = \Theta(g(N))，当且仅当f(N)=O(g(N))f(N) = O(g(N)) 且f(N)=Ω(g(N))f(N) = \Omega(g(N))，称f(N)f(N) 与g(N)g(N) 同阶

# NP 完全性理论

# P 类问题

多项式时间内可解决的问题

# NP 类问题

多项式时间内可验证的问题，NP 问题不要求给出一个算法来求解问题本身，而只要求给出一个确定性算法在多项式时间内验证它的解

# 递归与分治策略

# 递归的概念

  • 递归函数：用函数自身定义的函数，两要素：边界条件与递归方程
  • 递归算法：直接或间接调用自身的算法
  • 双递归函数：一个函数及它的一个变量是由函数自身定义（不能转换成循环）

# 排列问题

设 R={r1,r2,…,rn}R = \{r_1, r_2, \dots, r_n\} 是要进行排列的 nn 个元素，R=R−{r}R = R - \{r\}。集合 XX 中元素的全排列记为 Perm(X)Perm(X)。(r)Perm(X)(r)Perm(X) 表示在全排列 Perm(X)Perm(X) 的每个排列前加上前缀 rr 得到的排列。RR 的全排列可归纳定义如下：

  • 当 n=1n = 1 时，Perm(R)=(r)Perm(R) = (r)，其中 rr 是集合 RR 中唯一的元素；
  • 当 n>1n > 1 时，Perm(R)={r1Perm(R1),r2Perm(R2),…,rnPerm(Rn)}Perm(R) = \{ r_1 Perm(R_1), r_2 Perm(R_2), \dots, r_n Perm(R_n) \}。

依此递归定义，可设计产生 Perm(R)Perm(R) 的递归算法如下：

template <class T>
void Perm(T list[], int k, int m) { // 产生 list [ ] 数组中从 k 到 m 元素的全排列.
  if (k == m) {    // 只剩下一个元素
    for (int i = 0; i <= m; i++)
      cout << list[i];
    cout << endl;
  } else // 还有多个元素，递归产生排列
    for (int i = k; i <= m; i++) {
      swap(list[k], list[i]); // 固定第一个元素
      Perm(list, k + 1, m);
      swap(list[k], list[i]); // ! 还原，不然会有重复排列
    }
}

# 整数划分

将正整数 nn 表示成一系列正整数之和，n=n1+n2+⋯+nkn = n_1 + n_2 + \dots + n_k（n≥n1≥⋯≥nk≥1, k≥1n \geq n_1 \geq \dots \geq n_k \geq 1, \ k \geq 1）。正整数 nn 的这种表示称为正整数 nn 的划分。正整数 nn 的不同的划分个数称为正整数 nn 的划分数，记为 p(n)p(n)。

q(n,m)={1n=1,m=1q(n,n)n<m1+q(n,n−1)n=mq(n,m−1)+q(n−m,m)n>m>1q(n,m) = \begin{cases} 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{cases}

对于数据 n，最大加数 n1 不大于 m 的划分个数记作 q (n, m)。

int q(int n, int m) {
  // 如果 n 或 m 小于 1，没有有效的划分
  if ((n < 1) || (m < 1))
    return 0;
  // 如果 n 或 m 等于 1，只有一种划分方式
  if ((n == 1) || (m == 1))
    return 1;
  // 如果 n 小于 m，将 m 调整为 n，避免重复计算
  if (n < m)
    return q(n, n);
  // 如果 n 等于 m，增加一种包含 m 本身的划分
  if (n == m)
    return q(n, m - 1) + 1;
  // 递归计算不包含 m 的划分数量加上包含 m 的划分数量
  return q(n, m - 1) + q(n - m, m);
  // 示例说明：
  // q(6, 4) = q(6, 3) + q(2, 4)
  //q (n - m, m) 固定了 6 = 4 + x 中的 4，只对 x 进行讨论
}
# 递归的优缺点


    

  • 优点：

      

    • 算法简明；
      • 

    • 正确性易证明，是分析、设计的有力工具。
      • 

    

    • 

  • 缺点：

      

    • 执行效率不高；
      • 

    • 堆栈空间耗费
      • 

    

    • 



# 分治法


# 分治法所能解决的问题特征


    

  • 该问题可以分解为若干个规模较小的相同问题；
    • 

  • 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题；
    • 

  • 该问题的规模缩小到一定的程度就可以容易地解决；
    • 

  • 利用该问题分解出的子问题的解可以合并为该问题的解。
    • 



# 分治法基本思想


将规模为nn 的问题分解为kk 个规模较小的子问题，使这些子问题相互独立且与原问题相同，递归地解这些子问题，然后各个子问题的解合并得到原问题的解。


# 分治法基本步骤


Divide-and-Conquer(P):
  if |P| ≤ n₀:
    return Adhoc(P)
  divide P into P₁, P₂, ..., Pₖ
  for i from 1 to k:
    yᵢ = Divide-and-Conquer(Pᵢ)
  return Merge(y₁, y₂, ..., yₖ)
# 分治法求解过程


    

  1. 分解：把原问题分解为若干个规模较小、相互独立，与原问题相同的子问题；
    2. 

  2. 求解：若子问题规模较小且容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；
    3. 

  3. 合并：将已求解的各个子问题的解，逐步合并为原问题的解。
    4. 



# 分治法的时间复杂性


设T(n)T(n) 为规模为nn 的问题的解所需的时间，则有


T(n)≤{O(1)n=n0kT(nm)+f(n)n>n0T(n) \leq \begin{cases}
O(1) & n = n_0\\
kT(\frac{n}{m}) + f(n) & n > n_0
\end{cases}



其中，kk 为分解出的子问题个数，mm 为分解问题的规模，f(n)f(n) 为合并子问题解的时间


设n=man=m^a，则有a=log⁡mna=\log_m n，则有


ka=klog⁡mn=nlog⁡mkk^a=k^{\log_m n}=n^{\log_m k}



T(n)=nlog⁡mkT(1)+∑i=0log⁡mn−1kif(nmi)T(n) = n^{\log_m k}T(1) + \sum\limits_{i=0}^{\log_m n-1} k^i f(\frac{n}{m^i})



# 二分法


picture 17


template <class T>
int BinarySearch(T a[], const T &x, int n) {
  int left = 0, right = n - 1; // 初始化左右边界
  while (left <= right) { // 当左边界小于等于右边界时继续搜索
    int middle = (left + right) / 2; // 计算中间位置
    if (x == a[middle]) // 如果找到目标值，返回其位置
      return middle;
    if (x > a[middle]) // 如果目标值大于中间值，调整左边界
      left = middle + 1;
    else // 如果目标值小于中间值，调整右边界
      right = middle - 1;
  }
  return -1; // 如果未找到目标值，返回 - 1
}


    

  • 递推式：T(n)={O(1)n=1T(n2)+O(1)n>1T(n)=\begin{cases}O(1) & n=1\\T(\frac{n}{2})+O(1) & n>1\end{cases}
    • 

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





# 找金块


老板有一袋金块（共nn 块，nn 是 2 的幂（n≥2n≥2）），最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，希望用最少的比较次数找出最重和最轻的金块


auto findMaxandMin(vector<int> &gold) {
  // 如果数组只有两个元素，直接返回最大值和最小值
  if (gold.size() == 2) {
    return gold[0] > gold[1] ? make_pair(gold[0], gold[1])
                             : make_pair(gold[1], gold[0]);
  }
  // 将数组分成左右两部分
  vector<int> left(gold.begin(), gold.begin() + gold.size() / 2);
  vector<int> right(gold.begin() + gold.size() / 2, gold.end());
  // 递归求解左右两部分的最大值和最小值
  pair<int, int> leftMaxNMin = findMaxandMin(left);
  pair<int, int> rightMaxNMin = findMaxandMin(right);
  // 返回左右两部分的最大值和最小值
  return make_pair(max(leftMaxNMin.first, rightMaxNMin.first),
                   min(leftMaxNMin.second, rightMaxNMin.second));
}
# 棋盘覆盖


在一个2k×2k2^k \times 2^k 的棋盘中，有一个方格与其他方格不同，要求用 L 型骨牌覆盖其余方格

用分治法解决，将棋盘分为四个2k−1×2k−12^{k-1} \times 2^{k-1} 的子棋盘，分别覆盖，特殊方格必位于其中一个子棋盘中，其余三个子棋盘的特殊方格用 L 型骨牌覆盖


picture 13


picture 14


/**
  * @brief 棋盘覆盖
  * @param tr 棋盘左上角行号
  * @param tc 棋盘左上角列号
  * @param dr 特殊方格行号
  * @param dc 特殊方格列号
  * @param size 棋盘大小
  */
void ChessBoard(int tr, int tc, int dr, int dc, int size) {
  if (size == 1) return; // 基本情况：棋盘大小为 1 时，直接返回
  int t = tile++, s = size / 2; //t 表示当前 L 型骨牌编号，s 表示子棋盘的大小
  // 覆盖左上角子棋盘
  if (dr < tr + s && dc < tc + s)
    ChessBoard(tr, tc, dr, dc, s); // 特殊方格在左上角子棋盘
  else {
    board[tr + s - 1][tc + s - 1] = t; // 用 L 型骨牌覆盖右下角
    ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s); // 递归处理左上角子棋盘
  }
  // 覆盖右上角子棋盘
  if (dr < tr + s && dc >= tc + s)
    ChessBoard(tr, tc + s, dr, dc, s); // 特殊方格在右上角子棋盘
  else {
    board[tr + s - 1][tc + s] = t; // 用 L 型骨牌覆盖左下角
    ChessBoard(tr, tc + s, tr + s - 1, tc + s, s); // 递归处理右上角子棋盘
  }
  // 覆盖左下角子棋盘
  if (dr >= tr + s && dc < tc + s)
    ChessBoard(tr + s, tc, dr, dc, s); // 特殊方格在左下角子棋盘
  else {
    board[tr + s][tc + s - 1] = t; // 用 L 型骨牌覆盖右上角
    ChessBoard(tr + s, tc, tr + s, tc + s - 1, s); // 递归处理左下角子棋盘
  }
  // 覆盖右下角子棋盘
  if (dr >= tr + s && dc >= tc + s)
    ChessBoard(tr + s, tc + s, dr, dc, s); // 特殊方格在右下角子棋盘
  else {
    board[tr + s][tc + s] = t; // 用 L 型骨牌覆盖左上角
    ChessBoard(tr + s, tc + s, tr + s, tc + s, s); // 递归处理右下角子棋盘
  }
}
# 大整数的乘法


将nn 位二进制整数XX 和YY 都分为两段，每段的长为n2\frac{n}{2}。


picture 15


X=A×2n2+BY=C×2n2+DXY=AC×2n+(AD+BC)×2n2+BD\begin{align*}
X &= A \times 2^{\frac{n}{2}} + B \\
Y &= C \times 2^{\frac{n}{2}} + D \\
XY &= AC \times 2^n + (AD + BC) \times 2^{\frac{n}{2}} + BD
\end{align*}



时间复杂度为：


T(n)={O(1)n=14T(n2)+O(n)n>1  ⟹  T(n)=O(n2)T(n) = \begin{cases}
  O(1) & n=1\\
  4T(\frac{n}{2}) + O(n)& n>1
\end{cases}
\implies T(n) = O(n^2)





改进：


XY=AC×2n+((A−B)(D−C)+AC+BD)×2n2+BDXY = AC\times 2^n + ((A-B)(D-C)+AC+BD)\times 2^{\frac{n}{2}} + BD



时间复杂度：


T(n)={O(1)n=13T(n2)+O(n)n>1  ⟹  T(n)=O(nlog⁡3)=O(n1.59)T(n) = \begin{cases}
  O(1) & n=1\\
  3T(\frac{n}{2}) + O(n) & n>1
\end{cases}
\implies T(n) = O(n^{\log 3}) = O(n^{1.59})





auto Karatsuba(const string &X, const string &Y) {
  if (X.size() == 1) {
    return to_string(stoi(X) * stoi(Y));
  }
  string A = X.substr(0, X.size() / 2);
  string B = X.substr(X.size() / 2);
  string C = Y.substr(0, Y.size() / 2);
  string D = Y.substr(Y.size() / 2);
  string AC = Karatsuba(A, C);
  string BD = Karatsuba(B, D);
  string AD_BC = to_string((stoi(A) + stoi(B)) * (stoi(C) + stoi(D)) - stoi(AC) - stoi(BD));
  return to_string(stoi(AC) * pow(10, X.size()) + stoi(AD_BC) * pow(10, X.size() / 2) + stoi(BD));
}
# Strassen 矩阵乘法


将两个n×nn \times n 的矩阵分为四个n2×n2\frac{n}{2} \times \frac{n}{2} 的子矩阵，可将方程C=A×BC = A \times B 分解为


[C11C12C21C22]=[A11A12A21A22]×[B11B12B21B22]\begin{bmatrix}
C_{11} & C_{12} \\
C_{21} & C_{22}
\end{bmatrix}=
\begin{bmatrix}
A_{11} & A_{12} \\
A_{21} & A_{22}
\end{bmatrix}
\times
\begin{bmatrix}
B_{11} & B_{12} \\
B_{21} & B_{22}
\end{bmatrix}



时间复杂度：


T(n)={O(1)n=28T(n2)+O(n2)n>2  ⟹  T(n)=O(n3)T(n) = \begin{cases}
  O(1) & n=2\\
  8T(\frac{n}{2}) + O(n^2) & n>2
\end{cases}
\implies T(n) = O(n^3)





改进：将矩阵分解为七个n2×n2\frac{n}{2} \times \frac{n}{2} 的子矩阵，可将时间复杂度降为O(nlog⁡7)O(n^{\log 7})


M1=A11(B12−B22)M2=(A11+A12)B22M3=(A21+A22)B11M4=A22(B21−B11)M5=(A11+A22)(B11+B22)M6=(A12−A22)(B21+B22)M7=(A11−A21)(B11+B12)\begin{aligned}
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{aligned}



可得：


C11=M5+M4−M2+M6C12=M1+M2C21=M3+M4C22=M5+M1−M3−M7\begin{aligned}
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{aligned}



时间复杂度：


T(n)={O(1)n=27T(n2)+O(n2)n>2  ⟹  T(n)=O(nlog⁡7)=O(n2.81)T(n) = \begin{cases}
  O(1) & n=2\\
  7T(\frac{n}{2}) + O(n^2) & n>2
\end{cases}
\implies T(n) = O(n^{\log 7}) = O(n^{2.81})





# 合并排序


将一个数组分为两个规模相等的子数组，分别排序，然后将两个有序子数组合并为一个有序数组


void mergeSort(std::vector<int>& arr) {
    if (arr.size() <= 1)
        return;
    size_t mid = arr.size() / 2;
    std::vector<int> left(arr.begin(), arr.begin() + mid);
    std::vector<int> right(arr.begin() + mid, arr.end());
    mergeSort(left);
    mergeSort(right);
    std::merge(left.begin(), left.end(), right.begin(), right.end(), arr.begin());
}
// 一种 merge 实现
template <typename T>
void my_merge(const std::vector<T>& left, const std::vector<T>& right, std::vector<T>& result) {
    size_t i = 0, j = 0;
    result.reserve(left.size() + right.size());
    while(i < left.size() && j < right.size()) {
        if(left[i] <= right[j]) {
            result.push_back(left[i++]);
        }
        else {
            result.push_back(right[j++]);
        }
    }
    while(i < left.size()) {
        result.push_back(left[i++]);
    }
    while(j < right.size()) {
        result.push_back(right[j++]);
    }
}
时间复杂度：


T(n)={O(1)n=12T(n2)+O(n)n>1  ⟹  T(n)=O(nlog⁡n)T(n) = \begin{cases}
  O(1) & n=1\\
  2T(\frac{n}{2}) + O(n) & n>1
\end{cases}
\implies T(n) = O(n\log n)





改进：消除算法中的递归：自然归并排序


template <typename T>
void MergeSort(T a[], int n) {
  T *b = new T[n]; // 动态分配辅助数组
  int s = 1; // 初始子数组大小为 1
  while (s < n) {
    MergePass(a, b, s, n); // 将数组 a 中的子数组合并到 b 中
    s += s; // 子数组大小加倍
    MergePass(b, a, s, n); // 将数组 b 中的子数组合并到 a 中
    s += s; // 子数组大小加倍
  }
  delete[] b; // 释放辅助数组
}
template <typename T>
void MergePass(T a[], T b[], int s, int n) {
  int i = 0;
  while (i <= n - 2 * s) {
    Merge(a, b, i, i + s - 1, i + 2 * s - 1); // 合并相邻的两个子数组
    i = i + 2 * s; // 移动到下一个待合并的子数组
  }
  if (i + s < n) Merge(a, b, i, i + s - 1, n - 1); // 合并最后两个子数组
  else
    for (int j = i; j < n; j++) b[j] = a[j]; // 将剩余的元素复制到 b 中
}
template <typename T>
void Merge(T a[], T b[], int l, int m, int n) {
  int i = l, j = m + 1, k = l;
  while (i <= m && j <= n) {
    if (a[i] <= a[j])
      b[k++] = a[i++]; // 将较小的元素复制到 b 中
    else
      b[k++] = a[j++]; // 将较小的元素复制到 b 中
  }
  while (i <= m) b[k++] = a[i++]; // 将剩余的左半部分元素复制到 b 中
  while (j <= n) b[k++] = a[j++]; // 将剩余的右半部分元素复制到 b 中
}


# 快速排序


选取一个基准元素，将小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边，然后递归地对左右两部分进行排序


template <typename T>
int partition(T a[], int p, int r) {
  int i = p, j = r + 1;
  T x = a[p]; // 基准值 x
  while (true) {
    while (a[++i] < x && i < r)
      ; // 左指针 i 向右扫描
    while (a[--j] > x)
      ; // 右指针 j 向左扫描
    if (i >= j)
      break; // 当 i >= j 时退出循环
    swap(a[i], a[j]); // 交换 a [i] 和 a [j]
  }
  a[p] = a[j]; // 基准值放到最终位置
  a[j] = x;    //j 为基准值的位置
  return j;    // 返回基准值最终位置
}
template <typename T>
void quickSort(T a[], int l, int r) {
  if (l < r) {
    int pivot = partition(a, l, r);
    quickSort(a, l, pivot - 1);
    quickSort(a, pivot + 1, r);
  }
}
    

  1. 什么时候以 i > j  退出循环？什么时候以 i == j  退出循环？
    2. 





i > j  正常情况

 i == j  当  a[i]  和  a[j]  都等于基准值时（数组中有且只有奇数个等于基准值的元素）或数组递减




时间复杂度：


T(n)={O(1)n=1T(i−1)+T(n−i)+O(n)n>1  ⟹  T(n)=O(nlog⁡n)T(n) = \begin{cases}
  O(1) & n=1\\
  T(i-1)+T(n-i)+O(n) & n>1
\end{cases}
\implies T(n) = O(n\log n)





最坏情况下时间复杂度为


T(n)={O(1)n=1T(n−1)+O(n)n>1  ⟹  T(n)=O(n2)T(n) = \begin{cases}
  O(1) & n=1\\
  T(n-1)+O(n) & n>1
\end{cases}
\implies T(n) = O(n^2)







改进：随机化快速排序


template <typename T>
int RandomizedPartition(T a[], int l, int r) {
  int i = rand() % (r - l + 1) + l;
  swap(a[i], a[l]);
  return partition(a, l, r);
}
template <typename T>
void RandomizedQuickSort(T a[], int l, int r) {
  if (l < r) {
    int pivot = RandomizedPartition(a, l, r);
    RandomizedQuickSort(a, l, pivot - 1);
    RandomizedQuickSort(a, pivot + 1, r);
  }
}


# 线性时间选择


给定线性序列XX 和整数kk，求XX 中第kk 小的元素


思路：

随机选取一个元素作为基准元素，将小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边，若基准元素的位置为kk，则返回基准元素，否则递归地在左边或右边进行查找


template <typename T>
T RandomizedSelect(T a[], int low, int high, int k) {
  if (low == high) return a[low];
  int pivot = RandomizedPartition(a, low, high);
  int i = pivot - low + 1; // 前半部分元素个数
  if (k <= i) return RandomizedSelect(a, low, pivot, k);
  else return RandomizedSelect(a, pivot + 1, high, k - i);
}
时间复杂度：


T(n)={O(1)n=1T(n2)+O(n)n>1  ⟹  T(n)=O(n)T(n) = \begin{cases}
  O(1) & n=1\\
  T(\frac{n}{2})+O(n) & n>1
\end{cases}
\implies T(n) = O(n)





优化

选取基准点时，不是随机选取，而是选取中位数的中位数


    

  1. 将序列分为⌈n5⌉\lceil\frac{n}{5}\rceil 组，找出每组的中位数
    2. 

  2. 递归地找出这些中位数的中位数，以这个中位数的中位数作为基准点
    3. 



template <typename T>
T Select(T a[], int low, int high, int k) {
  if (high - low < 75) {
    sort(a + low, a + high + 1);
    return a[low + k - 1];
  }
  // 计算五元组的数量
  int numMedians = (high - low + 1 + 4) / 5;
  for (int i = 0; i < numMedians; i++) {
    // 获取五元组的起始和结束位置
    int subLow = low + i * 5;
    int subHigh = min(subLow + 4, high);
    // 对五元组进行排序
    sort(a + subLow, a + subHigh + 1);
    // 将五元组的中位数放到数组前部
    swap(a[low + i], a[subLow + (subHigh - subLow) / 2]);
  }
  // 递归调用 Select 获取中位数的中位数
  T pivot = Select(a, low, low + numMedians - 1, (numMedians + 1) / 2);
  // 按照主元 pivot 进行划分
  int idx = partition(a, low, high, pivot);
  int i = idx - low + 1;
  if (k == i)
    return a[idx];
  else if (k < i)
    return Select(a, low, idx - 1, k);
  else
    return Select(a, idx + 1, high, k - i);
}


# 最接近点对问题


# 一维最接近点对


给定一组一维坐标，求最接近的两个点


    

  1. 排序 O(nlog⁡n)O(n\log n)
    2. 

  2. 分治
    3. 

  3. 合并
    4. 



template <typename T> T ClosestPair(vector<T> &S) {
  auto len = S.size();
  if (len < 2)
    return numeric_limits<T>::max(); // 返回一个最大值表示无效情况
  auto m = len / 2;
  auto S1 = vector<T>(S.begin(), S.begin() + m);
  auto S2 = vector<T>(S.begin() + m, S.end());
  auto d1 = ClosestPair(S1);
  auto d2 = ClosestPair(S2);
  auto d3 = abs(S2.front() - S1.back());
  return min({d1, d2, d3});
}
时间复杂度：


T(n)={O(1)n<42T(n2)+O(nlog⁡n)n>=4  ⟹  T(n)=O(nlog⁡n)T(n) = \begin{cases}
  O(1) & n<4\\
  2T(\frac{n}{2})+O(n\log n) & n>=4
\end{cases}
\implies T(n) = O(n\log n)



# 二维最接近点对


给定平面上nn 个点，求最接近的两个点


选取一垂直线（x 坐标中位数）将平面分为两部分，分别求出两部分的最接近点对，

然后求出跨越垂直线的最接近点对，易证矩形中最多只有 6 个点


图 2


class Point {
public:
  double x, y;
  Point(double x, double y) : x(x), y(y) {}
  // 计算两个点的欧几里得距离
  auto operator-(const Point &p) const {
    return sqrt(pow(x - p.x, 2) + pow(y - p.y, 2));
  }
};
double ClosestPair2D(vector<Point> &S) {
  auto len = S.size();
  if (len < 2)
    return numeric_limits<double>::max(); // 无效情况，返回最大值
  if (len == 2)
    return S[0] - S[1];
  if (len == 3)
    return min({S[0] - S[1], S[1] - S[2], S[0] - S[2]});
  // 按 x 坐标排序
  sort(S.begin(), S.end(),
       [](const Point &a, const Point &b) { return a.x < b.x; });
  auto m = len / 2;
  auto S1 = vector<Point>(S.begin(), S.begin() + m); // 左半部分
  auto S2 = vector<Point>(S.begin() + m, S.end());   // 右半部分
  // 递归计算左右两部分的最小距离
  auto d1 = ClosestPair2D(S1);
  auto d2 = ClosestPair2D(S2);
  double d = min(d1, d2); // 获取左右两部分的最小距离
  // 查找分界线附近的最接近点对
  vector<Point> strip; // 存放 x 坐标在 d 范围内的点
  for (const auto &p : S) {
    if (abs(p.x - S[m].x) < d) {
      strip.push_back(p);
    }
  }
  // 按 y 坐标排序
  sort(strip.begin(), strip.end(),
       [](const Point &a, const Point &b) { return a.y < b.y; });
  // 查找 strip 中距离小于 d 的点对
  for (size_t i = 0; i < strip.size(); ++i) {
    for (size_t j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < d;
         ++j) {
      d = min(d, strip[i] - strip[j]);
    }
  }
  return d; // 返回最小距离
}
# 动态规划


# 动态规划的基本思想


与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

与分治法不同的是，适合用动态规划求解的问题，经分解得到的子问题往往不是相互独立的。


# 动态规划的实质


动态规划的实质是分治思想和解决冗余。


    

  1. 一种将问题实例分解为更小的、相似的子问题。
    2. 

  2. 存储子问题的解而避免计算重复的子问题。
    3. 



# 动态规划的特点


    

  • 动态规划法用于最优化问题，这类问题会有多种可能的解，而动态规划找出其中最优值的解。
    • 

  • 对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，以后再遇到时不必重新求解。
    • 



# 动态规划的基本步骤


    

  1. 分析最优解的性质，并刻划其结构特征；
    2. 

  2. 递归地定义最优值；
    3. 

  3. 以自底向上的方式计算出最优值；
    4. 

  4. 根据递归计算最优值时得到的信息，从子问题的最优解逐步构造出整个问题的最优解
    5. 



# 动态规划基本要素


# 最优子结构性质


当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。


A1,A2,⋯ ,An  ⟹  {A1,A2,⋯ ,AkAk+1,Ak+2,⋯ ,AnA_1,A_2,\cdots,A_n \implies \begin{cases}
  A_1,A_2,\cdots,A_{k}\\
  A_{k+1},A_{k+2},\cdots,A_n
\end{cases}



假设由最优解导出的其子问题的解不是最优的；

 构造出比原问题最优解更好的解；


# 重叠子问题性质


每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。


# 矩阵连乘问题


给定nn 个矩阵A1,A2,⋯ ,AnA_1,A_2,\cdots,A_n，其中AiA_i 与Ai+1A_{i+1} 是可乘的，求矩阵连乘的最优计算次序


定义A[i:j]A[i:j] 为Ai,Ai+1,⋯ ,AjA_i,A_{i+1},\cdots,A_j 的连乘积，m[i][j]m[i][j] 为计算A[i:j]A[i:j] 所需的标量乘法次数


# 分析最优解结构


设A[1:n]A[1:n] 的最优计算次序为A[1:k]A[k+1:n]A[1:k]A[k+1:n]，则有子矩阵链A[1:k]A[1:k] 和A[k+1:n]A[k+1:n] 的计算次序也应该是最优的。




反证法：

设A[1:n]=A[1:k]A[k+1:n]A[1:n]=A[1:k]A[k+1:n] 的计算次序是最优的，若存在一个计算次序A′[1:k]A'[1:k] 其需要的标量乘法次数少于A[1:k]A[1:k]，则A′[1:k]A[k+1:n]A'[1:k]A[k+1:n] 的计算次序也应该是最优的，与假设矛盾。

可以证明矩阵连乘问题具有最优子结构性质。




# 建立递归关系


m[i][j]={0i=jmin⁡i≤k<j{m[i][k]+m[k+1][j]+pi−1pkpj}i<jm[i][j]=\begin{cases}
  0 & i=j\\
  \min\limits_{i\leq k<j}\{m[i][k]+m[k+1][j]+p_{i-1}p_kp_j\} & i<j
\end{cases}



    

  1. 为什么是pi−1pkpjp_{i-1}p_kp_j？
    2. 





因为AiA_i 的维数为pi−1×pip_{i-1} \times p_i，AkA_k 的维数为pk−1×pkp_{k-1} \times p_k，AjA_j 的维数为pj−1×pjp_{j-1} \times p_j，所以AiAkAjA_iA_kA_j 的维数为pi−1×pjp_{i-1} \times p_j，所以需要pi−1pkpjp_{i-1}p_kp_j 次乘法




# 自底向上计算最优值


void MatrixChain(vector<int> &p, vector<vector<int>> &m,
                 vector<vector<int>> &s) {
  /**
    * p: 矩阵链的维数
    * m: 存储计算代价
    * s: 存储最优分割点
   */
  int n = p.size() - 1; // 矩阵链的长度
  for (int i = 1; i <= n; i++) {
    m[i][i] = 0; // 初始化对角线元素为 0，因为单个矩阵的计算代价为 0
  }
  for (int r = 2; r <= n; r++) { //r 表示当前考虑的矩阵链的长度，从 2 到 n
    for (int i = 1; i <= n - r + 1; i++) { //i 表示矩阵链的起始位置
      int j = i + r - 1; //j 表示矩阵链的结束位置
      m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; // 初始代价，假设最优分割点为 i
      s[i][j] = i; // 记录最优分割点
      for (int k = i + 1; k < j; k++) { // 遍历所有可能的分割点
        int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; // 计算当前分割点的代价
        if (t < m[i][j]) { // 如果当前代价小于已知最小代价
          m[i][j] = t; // 更新最小代价
          s[i][j] = k; // 更新最优分割点
        }
      }
    }
  }
}
# 构造最优解


void Traceback(vector<vector<int>> &s, int i, int j) {
  if (i == j) { // 如果 i 等于 j，说明矩阵链中只有一个矩阵
    cout << "A" << i; // 输出矩阵的标识符
    return;
  }
  cout << "("; // 输出左括号表示开始一个新的矩阵链
  Traceback(s, i, s[i][j]); // 递归处理第一个子链
  Traceback(s, s[i][j] + 1, j); // 递归处理第二个子链
  cout << ")"; // 输出右括号表示结束一个矩阵链
}
# 最长公共子序列


子序列：一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X={x1,x2,⋯ ,xm}X=\{x_1,x_2,\cdots,x_m\}，则另一个序列Z={z1,z2,⋯ ,zk}Z=\{z_1,z_2,\cdots,z_k\} 是XX 的子序列是指存在一个严格递增的序列{i1,i2,⋯ ,ik}\{i_1,i_2,\cdots,i_k\}，使得对于所有j=1,2,⋯ ,kj=1,2,\cdots,k，有zj=xijz_j=x_{i_j}。


# 最长公共子序列的结构


设序列X={x1,x2,…,xm}X = \{x_1,x_2,\dots,x_m\} 和Y={y1,y2,…,yn}Y = \{y_1,y_2,\dots,y_n\} 的最长公共子序列为Z={z1,z2,…,zk}Z=\{z_1,z_2,\dots,z_k\}，则


    

  1. 若xm=ynx_m=y_n，则zk=xm=ynz_k=x_m=y_n，且Zk−1Z_{k-1} 是Xm−1X_{m-1} 和Yn−1Y_{n-1} 的最长公共子序列
    2. 

  2. 若xm≠ynx_m\neq y_n 且zk≠xmz_k\neq x_m，则ZZ 是Xm−1X_{m-1} 和YY 的最长公共子序列
    3. 

  3. 若xm≠ynx_m\neq y_n 且zk≠ynz_k\neq y_n，则ZZ 是XX 和Yn−1Y_{n-1} 的最长公共子序列
    4. 





证明：


    

  1. 如果zk≠xmz_k\neq x_m，那么可以将xm=ynx_m=y_n 加入到ZZ 中，得到一个更长的公共子序列，与ZZ 的定义矛盾。因此必然有xm=yn=zkx_m=y_n=z_k。由此可知，Zk−1Z_{k-1} 是Xm−1X_{m-1} 和Yn−1Y_{n-1} 的最长公共子序列。若Xm−1X_{m-1} 和Yn−1Y_{n-1} 有长度大于k−1k-1 的公共子序列WW，则将xmx_m 加在WW 的末尾，得到一个长度大于kk 的公共子序列，与ZZ 的定义矛盾。
    2. 

  2. 如果zk≠xmz_k\neq x_m，那么ZZ 是Xm−1X_{m-1} 和YY 的最长公共子序列。若Xm−1X_{m-1} 和YY 有长度大于kk 的公共子序列WW，那么WW 也是XX 和YY 的公共子序列，与ZZ 的定义矛盾。
    3. 

  3. 同理，ZZ 是XX 和Yn−1Y_{n-1} 的最长公共子序列。
    4. 





# 子问题的递归结构


设c[i][j]c[i][j] 为XiX_i 和YjY_j 的最长公共子序列的长度，则有


c[i][j]={0i=0或j=0c[i−1][j−1]+1i,j>0且xi=yjmax⁡{c[i][j−1],c[i−1][j]}i,j>0且xi≠yjc[i][j]=\begin{cases}
  0 & i=0\text{或}j=0\\
  c[i-1][j-1]+1 & i,j>0\text{且}x_i=y_j\\
  \max\{c[i][j-1],c[i-1][j]\} & i,j>0\text{且}x_i\neq y_j
\end{cases}



# 计算最优值


void LCSLength(const string &X, const string &Y, vector<vector<int>> &c,
               vector<vector<string>> &b) {
  int m = X.size();
  int n = Y.size();
  // for (int i = 1; i <= m; i++) {
  //   c[i][0] = 0;
  // }
  // for (int j = 0; j <= n; j++) {
  //   c[0][j] = 0;
  // }
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (X[i - 1] == Y[j - 1]) { // 注意这里的下标，因为 X 和 Y 的下标是从 0 开始的，所以要减 1
        c[i][j] = c[i - 1][j - 1] + 1;
        b[i][j] = "↖";
      } else if (c[i - 1][j] >= c[i][j - 1]) {
        c[i][j] = c[i - 1][j];
        b[i][j] = "↑";
      } else {
        c[i][j] = c[i][j - 1];
        b[i][j] = "←";
      }
    }
  }
}
# 构建 LCS


string LCS(const string &X, const string &Y, const vector<vector<string>> &b,
           int i, int j) {
  if (i == 0 || j == 0) {
    return "";
  }
  if (b[i][j] == "↖") {
    return LCS(X, Y, b, i - 1, j - 1) + X[i - 1];
  } else if (b[i][j] == "↑") {
    return LCS(X, Y, b, i - 1, j);
  } else {
    return LCS(X, Y, b, i, j - 1);
  }
}


↑ 和 ← 只指引构造 LCS 的方向，不是 LCS 的一部分，只有 ↖ 才是 LCS 的一部分。




# 算法改进


省去 b  数组，直接构造 LCS


string LCSWithoutB(const string &X, const string &Y) {
  int m = X.size();
  int n = Y.size();
  vector<vector<int>> c(m + 1, vector<int>(n + 1, 0));
  for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
      if (X[i - 1] == Y[j - 1]) {
        c[i][j] = c[i - 1][j - 1] + 1;
      } else {
        c[i][j] = max(c[i - 1][j], c[i][j - 1]);
      }
    }
  }
  string lcs;
  int i = m, j = n;
  while (i > 0 && j > 0) {
    if (X[i - 1] == Y[j - 1]) {
      lcs = X[i - 1] + lcs;
      i--;
      j--;
    } else if (c[i - 1][j] >= c[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }
  return lcs;
}
只计算 LCS 的长度，不构造 LCS，仅用一维 dp


int LCSLengthOnly(const string &X, const string &Y) {
  //m 保存字符串 X 的长度
  int m = X.size();
  //n 保存字符串 Y 的长度
  int n = Y.size();
  // 创建一个大小为 (n+1) 的一维数组 'c'，初始值为 0。
  // 该数组用于存储到目前为止，X 和 Y 每个位置的最长公共子序列长度。
  vector<int> c(n + 1, 0);
  // 遍历字符串 X 的每一个字符
  for (int i = 1; i <= m; i++) {
    // 'prev' 保存上一次 i 循环中 c [j-1] 的值 (上一行)
    int prev = 0;
    // 遍历字符串 Y 的每一个字符
    for (int j = 1; j <= n; j++) {
      // 'temp' 临时保存当前 c [j] 的值，在它被更新前
      int temp = c[j];
      // 如果字符相同，则当前位置的 LCS 长度增加 1
      if (X[i - 1] == Y[j - 1]) {
        c[j] = prev + 1;
      } else {
        // 如果字符不同，则取当前列和前一列的最大值
        c[j] = max(c[j], c[j - 1]);
      }
      // 更新 prev 为 c [j] 原来的值
      prev = temp;
    }
  }
  // 返回最终的 LCS 长度
  return c[n];
}
# 最大子段和


给定由nn 个整数组成的序列a1,a2,⋯ ,ana_1,a_2,\cdots,a_n，求该序列形如∑k=ijak\sum\limits_{k=i}^{j}a_k 的连续子段的最大和，当所有整数均为负数时，最大子段和为 0。


定义 dp[i]  为max⁡1≤j≤i∑k=jiak\max\limits_{1\leq j\leq i}\sum\limits_{k=j}^{i}a_k，即以1−i1-i 为左端点，以ii 为右端点的最大子段和。


当 dp[i-1] >= 0  时， dp[i] = dp[i-1] + a[i] ，否则 dp[i] = a[i] 。


dp[i]={0i=0max⁡{dp[i−1]+a[i],a[i]}i≤1dp[i]=\begin{cases}
  0 & i=0\\
  \max\{dp[i-1]+a[i],a[i]\} & i\leq 1
\end{cases}



auto LSS(vector<int> a) {
  vector<int> dp(a.size() + 1);
  dp[0] = 0;
  for (int i = 1; i <= a.size(); i++) {
    dp[i] = max(dp[i - 1] + a[i - 1], a[i - 1]);
  }
  auto res = max_element(dp.begin(), dp.end());
  return *res;
}
// 状态压缩
auto LSS2(vector<int> a) {
  int dp = 0, res = 0;
  for (const auto &x: a) {
    dp = dp > 0 ? dp + x : x;
    res = max(res, dp);
  }
  return res;
}
# 凸多边形三角剖分


给定一个凸多边形以及定义在由多边形的边和弦组成的三角形上的权函数ω\omega，将其分割成若干个三角形，使得分割后的三角形的总的权值和最小。


图 3


定义dp[i][j]dp[i][j] 为凸子多边形{vi−1,vi,⋯ ,vj}\{v_{i-1}, v_i,\cdots, v_j\} 的最优三角剖分的权值和，


dp[i][j]={0j=imin⁡i<=k<j{dp[i][k]+dp[k+1][j]+ω(vi−1,vk,vj)}j>idp[i][j]=\begin{cases}
  0 & j=i\\
  \min\limits_{i<=k<j}\{dp[i][k]+dp[k+1][j]+\omega(v_{i-1},v_k,v_j)\} & j>i
\end{cases}



void MinWeightTriangulation(vector<vector<double>> &dp, vector<vector<int>> &s) {
  int n = dp.size() - 2; // 边数 = 多边形的顶点数 - 1
  for (int i = 1; i <= n; i++) {
    dp[i][i] = 0;
  }
  for (int r = 2; r <= n; r++) {
    for (int i = 1; i <= n - r + 1; i++) {
      auto j = i + r - 1;
      dp[i][j] = dp[i + 1][j] + w(i - 1, i, j);
      s[i][j] = i;
      for (int k = i + 1; k < j; k++) {
        auto t = dp[i][k] + dp[k + 1][j] + w(i - 1, k, j);
        if (t < dp[i][j]) {
          dp[i][j] = t;
          s[i][j] = k;
        }
      }
    }
  }
}
# 图像压缩


数字化图像是n×nn\times n 的像素阵列。 假定每个像素有一个 0~255 的灰度值，存储一个像素需 8 位。 为了减少存储空间，采用变长模式，即不同像素用不同位数来存储。


将像素分成连续的mm 段S1,S2,⋯ ,SmS_1,S_2,\cdots,S_m，使每段中的像素存储位数相同。第ii 段的存储像素数为 l[i] ，且该段中的每个像素只用 b[i]  表示。


存储空间为∑i=1ml[i]×b[i]+11m\sum\limits_{i=1}^{m}l[i]\times b[i]+11m，其中 11m 为存储段的信息所需的位数。


# 图像压缩的最优子结构


设l[i],b[i],1≤i≤ml[i],b[i],1\leq i\leq m 是{p1,p2,⋯ ,pi}\{p_1,p_2,\cdots,p_i\} 一个最优方案，显然l[1],b[1]l[1],b[1] 是{p1,⋯ ,pl[1]}\{p_1,\cdots,p_{l[1]}\} 的最优方案，且l[i],b[i],2≤i≤ml[i], b[i], 2\leq i \leq m 是{pl[i]+1,⋯ ,pn}\{p_{l[i]+1},\cdots,p_{n}\} 的最优方案。


# 图像压缩的递归结构


设s[i]s[i] 为{p1,p2,⋯ ,pi}\{p_1,p_2,\cdots,p_i\} 的最优存储位数


    

  1. 考察最后一个元素pip_i 的分段情况​
    2. 

  2. 假设 pip_i 自成一段，则 S[i]=s[i−1]+保存 pi 的代价S[i] = s[i-1] + \text{保存 } p_i \text{ 的代价}；
    3. 

  3. 假设最后 2 个像素点为一段，则 s[i]=s[i−2]+保存最后 2 个像素点的代价s[i] = s[i-2] + \text{保存最后 2 个像素点的代价}；
    4. 

  4. 假设最后 ii 个像素点为一段，则 s[i]=s[0]+保存最后 i 个像素点的代价s[i] = s[0] + \text{保存最后 } i \text{ 个像素点的代价}；
    5. 

  5. 取 s[i]s[i] 为 min⁡\min 时对应的元素个数。假设为 kk。
    6. 

  6. 此时，则 S[i]=s[i−k]+保存最后 k 个像素的代价S[i] = s[i-k] + \text{保存最后 } k \text{ 个像素的代价}；
    7. 

  7. 后者 =k×max⁡{k 个灰度值二进制位数}+11= k \times \max\{\text{k 个灰度值二进制位数}\} + 11；
    8. 

  8. 求解 s[i−k]s[i-k] 即可；
    9. 

  9. 考察最后一个像素点的分段情况，自成 1 段？后 2 个点？后 3 个点？…… 重复上述过程。
    10. 



s[n]=min⁡1≤k≤min⁡{n,256}{s[n−k]+k×amax⁡(n−k+1,n)}+11amax⁡(i,j)=⌈log⁡2(max⁡i≤k≤j{pk}+1)⌉\begin{align*}
  &s[n] = \min\limits_{1\leq k\leq\min\{n,256\}}\{s[n-k]+k\times a\max(n-k+1,n)\}+11\\
  &a\max(i,j) = \lceil\log_2(\max\limits_{i \leq k \leq j}\{p_k\} + 1)\rceil
\end{align*}



    

  • l[i] ：前 i 个像素点最后一段包含的个数。
    • 

  • b[i] ：前 i 个像素点最后一段位数 / 最大值。
    • 

  • a[i] ：第 i 个像素点的位数。
    • 



int length(int x) {
  int l = 1;
  x >>= 1;
  while (x > 0) {
    l++;
    x >>= 1;
  }
  return l;
}
void ImageCompression(vector<int> &p, vector<int> &l, vector<int> &b,
      vector<int> &s) {
  const int n = p.size();
  constexpr int L_MAX = 256, HEADER = 11; // 定义最大块长度和头部长度
  s[0] = 0;
  vector<int> a(n, 0);
  // 计算每个像素值的位数，存储在数组 a 中
  for (int i = 0; i < n; i++) { // 遍历所有像素
    a[i] = length(p[i]); //length () 函数计算 p [i] 的二进制位数
    int bMax = numeric_limits<int>::min(); // 初始化当前块中位数的最大值
    s[i] = numeric_limits<int>::max(); // 初始化 s [i] 为最大整数
    // 考虑从位置 i 向前的不同块大小 j
    for (int j = 1; j <= i + 1 && j <= L_MAX; j++) { //j 是当前块的长度
      // 更新当前块中像素位数的最大值
      bMax = max(bMax, a[i - j + 1]); // 在当前块中找到最大的位数
      // 计算将当前块划分为长度为 j 的块后的总存储位数，并与之前的最小值比较
      if (s[i] > s[i - j] + j * bMax) {
        s[i] = s[i - j] + j * bMax; // 更新最小存储位数
        l[i] = j; // 记录当前最优块的长度
        b[i] = bMax; // 记录当前最优块的位数
      }
    }
    s[i] += HEADER; // 加上存储段信息所需的位数
  }
}
# 电路布线


一块电路板的上下两端分别有nn 个引脚，用导线(i,π(i))(i, \pi(i)) 连接引脚ii 和π(i)\pi(i)，其中π\pi 是一个排列。第ii 条连线和第jj 条连线相交当且仅当π(i)>π(j)\pi(i) > \pi(j) 且i<ji < j。要求确定导线集的最大不相交子集。


图 4


化为多步决策，自底向上，先求出​只有一条连线的最大不相交子集，再求有 2 条连线的最大不相交子集...


# 电路布线的最优子结构


记N(i,j)={t∣(t,π(t))∈Nets,t≤i,π(t)≤j}N(i,j) = \{t|(t, \pi(t)) \in Nets, t \leq i, \pi(t) \leq j\}，N(i,j)N(i,j) 的最大不相交子集为MNS(i,j)MNS(i,j)，Size(i,j)=∣MNS(i,j)∣Size(i,j) = |MNS(i,j)|。


    

  • 当i=1i = 1 时，有MNS(i,j)=N(1,j)={∅j<π(1){1,π(1)}j≥π(1)MNS(i,j) = N(1, j) = \begin{cases}\varnothing & j < \pi(1)\\ \{1, \pi(1)\} & j \geq \pi(1)\end{cases}
    • 

  • 当i>1i > 1 时，有

      

    • 若j<π(i)j < \pi(i)。此时(i,π(i))∉N(i,j)(i, \pi(i)) \notin N(i,j)，所以N(i,j)=N(i−1,j)N(i,j) = N(i-1,j)，Size(i,j)=Size(i−1,j)Size(i,j) = Size(i-1,j)
      • 

    • 若j≥π(i)j \geq \pi(i)。若(i,π(i))∈MNS(i,j)(i, \pi(i)) \in MNS(i,j)，则对任意(t,π(t))∈MNS(i,j)(t, \pi(t)) \in MNS(i,j)，有t<it < i，π(t)<π(i)\pi(t) < \pi(i)，否则(t,π(t))(t, \pi(t)) 和(i,π(i))(i, \pi(i)) 相交。所以MNS(i,j)−{(i,π(i))}MNS(i,j) - \{(i, \pi(i))\} 是N(i−1,π(i)−1)N(i-1, \pi(i)-1) 的最大不相交子集，否则MNS(i−1,π(i)−1)∪{(i,π(i))}⊆N(i,j)MNS(i-1, \pi(i)-1)\cup\{(i, \pi(i))\} \subseteq N(i,j) 是比MNS(i,j)MNS(i,j) 更大的不相交子集，这与MNS(i,j)MNS(i,j) 的定义矛盾。若(i,π(i))∉MNS(i,j)(i, \pi(i)) \notin MNS(i,j)，则对任意(t,π(t))∈MNS(i,j)(t, \pi(t)) \in MNS(i,j)，有t<it < i，从而MNS(i,j)/subseteqN(i−1,j)MNS(i,j)/subseteq N(i-1,j)，因此Size(i,j)/leqSize(i−1,j)Size(i,j) /leq Size(i-1,j)。另一方面，MNS(i−1,j)⊆N(i,j)MNS(i-1,j) \subseteq N(i,j)，所以Size(i,j)≥Size(i−1,j)Size(i,j) \geq Size(i-1,j)，则Size(i,j)=Size(i−1,j)Size(i,j) = Size(i-1,j)。
      • 

    

    • 



# 递归计算最优值


    

  • 当i=1i = 1 时，Size(1,j)={0j<π(1)1j≥π(1)Size(1,j) = \begin{cases}0 & j < \pi(1)\\ 1 & j \geq \pi(1)\end{cases}
    • 

  • 当i>1i > 1 时，Size(i,j)={Size(i−1,j)j<π(i)max⁡{Size(i−1,j),Size(i−1,π(i)−1)+1}j≥π(i)Size(i,j) = \begin{cases}Size(i-1,j) & j < \pi(i)\\ \max\{Size(i-1,j), Size(i-1, \pi(i)-1)+1\} & j \geq \pi(i)\end{cases}
    • 



// C[0:n]
void MNS(const vector<int> &C, vector<vector<int>> &size) {
  const int n = C.size();
  for (int j = 0; j < n; j++) {
    size[0][j] = j < C[0] ? 0 : 1;
  }
  for (int i = 1; i < n - 1; i++) {
    for (int j = 0; j < n; j++) {
      if (j < C[i]) {
        size[i][j] = size[i - 1][j];
      } else {
        size[i][j] = max(size[i - 1][j], size[i - 1][C[i] - 1] + 1);
      }
    }
  }
  size[n - 1][n - 1] = max(size[n - 2][n - 1], size[n - 2][C[n - 1] - 1] + 1);
}
# 构造最优解


auto Traceback(const vector<vector<int>> &size, const vector<int> &C) {
  vector<int> Net;
  int j = C.size() - 1;
  int m = 0;
  for (int i = C.size() - 1; i > 0; i--) {
    if (size[i][j] != size[i - 1][j]) {
      Net[m++] = i;
      j = C[i] - 1;
    }
  }if (j >= C[0]) {
      Net[m++] = 0;
    }
  return Net;
}
# 流水线作业调度


nn 个作业{1,2,⋯ ,n}\{1,2,\cdots,n\} 要在 2 台相同的流水线上加工，每个作业加工顺序为先在M1M_1 上加工，再在M2M_2 上加工。第ii 个作业在M1M_1 上加工时间为aia_i，在M2M_2 上加工时间为bib_i。


最优调度方案是使得M1M_1 没有空闲时间，M2M_2 的空闲时间最小。


设全部作业集合为N={1,2,⋯ ,n}N = \{1,2,\cdots,n\}，S⊆NS \subseteq N 是一个作业子集。在一般情况下，机器M1M_1 开始加工SS 中作业时，机器M2M_2 还在加工其他作业，要等时间tt 后才可利用。这种情况下完成SS 中作业所需的最短时间记为T(S,t)T(S, t)。

流水作业调度问题的最优值为T(N,0)T(N, 0)。


# 流水线作业调度的最优子结构


设π\pi 是所给nn 个作业的一个最优调度方案，所需加工时间为aπ(1)+T′a_{\pi(1)} + T'。其中T′T' 是在机器M2M_2 的等待时间为bπ(1)b_{\pi(1)} 时，安排作业π(2),π(3),⋯ ,π(n)\pi(2),\pi(3),\cdots,\pi(n) 所需的时间。记S=N−{π(1)}S=N-\{\pi(1)\}，则T′=T(S,bπ(1))T' = T(S, b_{\pi(1)})。


# 流水线作业调度的递归计算最优值


T(N,0)=min⁡1≤i≤n{ai+T(N−{i},bi)}T(N, 0) = \min\limits_{1\leq i\leq n}\{a_i + T(N-\{i\}, b_i)\}，推广到一般情况有：


T(S,t)=min⁡i∈S{ai+T(S−{i},bi+max{t−ai,0})}T(S,t) = \min \limits_{i \in S} \{a_i+T(S-\{i\}, b_i+max\{t-a_i,0\})\}



式中， max⁡{t−ai,0}\max\{t-a_i, 0\} 项是由于在机器M2M_2 上，作业 i 必须在max⁡{t,ai}\max\{t,a_i\} 时间之后才能开工。因此在机器M1M_1 上完成作业 i 之后在机器上还需要bi+max⁡{t,ai}−ai=bi+max⁡{t−ai,0}b_i+\max\{t,a_i\} - a_i = b_i + \max\{t-a_i, 0\} 时间才能完成对作业 i 的加工。


# 流水线作业调度的 Johnson 法则


如果作业ii 和作业jj 满足min⁡{bi,aj}≥min⁡{bj,ai}\min\{b_i, a_j\} \geq \min\{b_j, a_i\}，则作业ii 应该在作业jj 之前加工。




nn 个任务的 Johnson 法则


    

  1. 令N1={i∣ai<bi}N_1 = \{i|a_i < b_i\}，N2={i∣ai≥bi}N_2 = \{i|a_i \geq b_i\}；
    2. 

  2. 按照aia_i 的非降序排列N1N_1 中的任务，按照bib_i 的非升序排列N2N_2 中的任务；
    3. 

  3. N1N_1 中的任务在N2N_2 中的任务之前加工。
    4. 





vector<int> flowShop(const vector<int> &a, const vector<int> &b) {
  const int n = a.size();
  vector<int> C(n);
  vector<pair<int, int>> tasks(n);
  for (int i = 0; i < n; i++) {
    tasks[i] = {a[i], b[i]};
  }
  vector<int> N1, N2;
  for (int i = 0; i < n; i++) {
    if (tasks[i].first < tasks[i].second) {
      N1.push_back(i);
    } else {
      N2.push_back(i);
    }
  }
  sort(N1.begin(), N1.end(),
       [&](int i, int j) { return tasks[i].first < tasks[j].first; });
  sort(N2.begin(), N2.end(),
       [&](int i, int j) { return tasks[i].second > tasks[j].second; });
  move(N1.begin(), N1.end(), C.begin());
  move(N2.begin(), N2.end(), C.begin() + N1.size());
  return C;
}
# 流水线作业调度的总时间


int calculateTime(vector<int> C, const vector<int> &a, const vector<int> &b) {
    const int n = C.size();
    vector<int> f(n);
    vector<int> g(n);
    f[0] = a[C[0]];
    g[0] = f[0] + b[C[0]];
    for (int i = 1; i < n; i++) {
        f[i] = f[i - 1] + a[C[i]];
        g[i] = max(g[i - 1], f[i]) + b[C[i]];
    }
    return g[n - 1];
}
# 0-1 背包问题


给定nn 个物品，每个物品的重量为wiw_i，价值为viv_i，背包的容量为cc，求如何装入背包使得背包中物品的总价值最大。


形式化描述为：给定c>0,wi>0,vi>0,i=1,2,⋯ ,nc>0, w_i>0, v_i>0, i=1,2,\cdots,n，求一个向量x=(x1,x2,⋯ ,xn)x=(x_1,x_2,\cdots,x_n)，其中xi∈{0,1}x_i\in\{0,1\}，使得∑i=1nwixi≤c\sum\limits_{i=1}^{n}w_ix_i\leq c 且∑i=1nvixi\sum\limits_{i=1}^{n}v_ix_i 最大，即


{max⁡∑i=1nvixis.t.∑i=1nwixi≤cxi∈{0,1}i=1,2,⋯ ,n\begin{cases}
  \max & \sum\limits_{i=1}^{n}v_ix_i\\
  s.t. & \sum\limits_{i=1}^{n}w_ix_i\leq c\\
  & x_i\in\{0,1\} & i=1,2,\cdots,n
\end{cases}



# 0-1 背包问题的最优子结构


设(y1,y2,⋯ ,yn)(y_1,y_2,\cdots,y_n) 是一个最优解，则(y2,y3,⋯ ,yn)(y_2,y_3,\cdots,y_n) 是下面相应子问题的一个最优解：


{max⁡∑i=2nvixis.t.∑i=2nwixi≤c−wiy1xi∈{0,1}i=2,3,⋯ ,n\begin{cases}
  \max & \sum\limits_{i=2}^{n}v_ix_i\\
  s.t. & \sum\limits_{i=2}^{n}w_ix_i\leq c-w_iy_1\\
  & x_i\in\{0,1\} & i=2,3,\cdots,n
\end{cases}



否则，设(z2,z3,⋯ ,zn)(z_2,z_3,\cdots,z_n) 是上述子问题的一个最优解，则(y2,y3,⋯ ,yn)(y_2,y_3,\cdots,y_n) 不是它的一个最优解。由此可知，∑i=2nvizi>∑i=2nviyi\sum\limits_{i=2}^{n}v_iz_i > \sum\limits_{i=2}^{n}v_iy_i，且w1y1+∑i=2nwizi≤cw_1y_1 + \sum\limits_{i=2}^{n}w_iz_i \leq c。因此


v1y1+∑i=2nvizi>∑i=1nviyiw1y1+∑i=2nwizi≤c\begin{align*}
  v_1y_1 + \sum\limits_{i=2}^{n}v_iz_i &> \sum\limits_{i=1}^{n}v_iy_i \\
w_1y_1 + \sum\limits_{i=2}^{n}w_iz_i &\leq c
\end{align*}



这说明(y1,z2,z3,⋯ ,zn)(y_1,z_2,z_3,\cdots,z_n) 是原问题的一个最优解。从而(y1,y2,⋯ ,yn)(y_1,y_2,\cdots,y_n) 不是原问题的一个最优解，这与假设矛盾。


# 0-1 背包问题的递归计算最优值


设所给 0-1 背包的子问题的最优值为m(i,j)m(i, j)，即可选择物品为{i,i+1,⋯ ,n}\{i, i+1,\cdots,n\}，背包容量为jj 时的最优值。则有


m(i,j)={max{m(i+1,j),m(i+1,j−wi)+vi}j≥wim(i+1,j)j<wim(i, j) = \begin{cases}
  max\{m(i+1, j), m(i+1, j-w_i)+v_i\} & j\geq w_i\\
  m(i+1, j) & j < w_i
\end{cases}



// 下标从 1 开始
void knapsack(const vector<int> &w, const vector<int> &v, int c,
              vector<vector<int>> &m) {
  const int n = w.size();
  for (int j = 0; j <= min(c, w[n - 1]); j++) {
    m[n][j] = 0;
  }
  for (int j = w[n]; j <= c; j++) {
    m[n][j] = v[n];
  }
  for (int i = n - 1; i > 1; i--) {
    for (int j = 0; j <= min(c, w[i - 1]); j++) {
      m[i][j] = m[i + 1][j];
    }
    for (int j = w[i]; j <= c; j++) {
      m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i]);
    }
  }
  if (c >= w[1]) {
    m[1][c] = max(m[1][c], m[2][c - w[1]] + v[1]);
  }
  else {
    m[1][c] = m[2][c];
  }
}
void Traceback(const vector<vector<int>> &m, const vector<int> &w,
               const vector<int> &v, int c, vector<int> &x) {
  const int n = w.size();
  for (int i = 1; i < n; i++) {
    if (m[i][c] == m[i + 1][c]) {
      x[i] = 0;
    } else {
      x[i] = 1;
      c -= w[i];
    }
  }
  x[n] = m[n][c] > 0 ? 1 : 0;
}
# 0-1 背包问题的跳跃点解法


p[i]={(j,m(i,j))∣0≤j≤c}p[i] = \{(j, m(i, j))|0\leq j\leq c\}，p[i]p[i] 是一个有序对的集合，其中jj 是背包容量，m(i,j)m(i, j) 是选择物品{i,i+1,⋯ ,n}\{i, i+1,\cdots,n\}，背包容量为jj 时的最优值。


m(i,j)m(i,j) 的全部跳跃点p[i]p[i] 包含于​m(i+1,j)m(i+1,j) 的跳跃点集p[i+1]p[i+1] 与m(i+1,j−wi)+vim(i+1,j-w_i)+v_i 的跳跃点集q[i+1]q[i+1] 的并集中​


p[i]⊆p[i+1]∪q[i+1]q[i+1]=p[i+1]⊕(wi,vi)={(j+wi,m(i,j)+vi)∣(j,m(i,j))∈p[i+1]}\begin{align*}
p[i] &\subseteq p[i+1] \cup q[i+1]\\
q[i+1] &= p[i+1] \oplus  (w_i, v_i) \\
       &= \{(j+w_i, m(i, j)+v_i) \mid (j, m(i, j)) \in p[i+1]\}
\end{align*}



设(a,b)(a,b) 和(c,d)(c,d) 是p[i+1]∪q[i+1]p[i+1] \cup q[i+1] 中的两个跳跃点，当c≥ac \geq a 且d<bd < b 时，(c,d)(c, d) 是(a,b)(a, b) 的一个受控点，需要删掉。


图 5


图中(5,4)(5,4) 是(4,6)(4,6) 的一个受控点，需要删掉。


# 贪心算法


# 活动安排问题


设有nn 个活动的集合E={1,2,⋯ ,n}E=\{1,2,\cdots,n\}，每个活动ii 都有一个使用该资源的起始时间sis_i 和一个结束时间fif_i，且0≤si<fi<∞0\leq s_i < f_i < \infty。如果选择活动ii，则活动ii 发生在半开时间区间