第一章 算法概述

五种算法渐进界

1. O (Big-O) —— 渐近上界

设 f(n) 和 g(n) 是定义在非负整数上的正函数。 如果存在正常数 c 和 n0，使得对于所有的 n ≥ n0，都有：

0 ≤ f(n) ≤ c ⋅ g(n)

则称 f(n) = O(g(n))。

2. Ω (Big-Omega) —— 渐近下界

设 f(n) 和 g(n) 是定义在非负整数上的正函数。 如果存在正的常数 c 和 n0，使得对于所有的 n ≥ n0，都有：

0 ≤ c ⋅ g(n) ≤ f(n)

则称 f(n) = Ω(g(n))。

3. Θ (Big-Theta) —— 渐近紧确界

设 f(n) 和 g(n) 是定义在非负整数上的正函数。 如果存在正的常数 c1, c2 和 n0，使得对于所有的 n ≥ n0，都有：

0 ≤ c1 ⋅ g(n) ≤ f(n) ≤ c2 ⋅ g(n)

则称 f(n) = Θ(g(n))。

4. o (Little-o) —— 非紧确上界

设 f(n) 和 g(n) 是定义在非负整数上的正函数。 如果对于任意正的常数 c > 0，都存在 n0，使得对于所有的 n ≥ n0，都有：

0 ≤ f(n) < c ⋅ g(n)

则称 f(n) = o(g(n))。 (等价定义：$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$)，通常证明时使用极限

5. ω (Little-omega) —— 非紧确下界

设 f(n) 和 g(n) 是定义在非负整数上的正函数。 如果对于任意正的常数 c > 0，都存在 n0，使得对于所有的 n ≥ n0，都有：

0 ≤ c ⋅ g(n) < f(n)

则称 f(n) = ω(g(n))。 (等价定义：$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$)，通常证明时使用极限

解递归方程

在算法分析中，递归方程主要分为两类：

  1. 线性递推式 （如斐波那契数列）：an = c1an − 1 + c2an − 2 + …
  2. 分治递归式 （如归并排序）：T(n) = aT(n/b) + f(n)

一、 常系数线性齐次递推方程

形式： an + c1an − 1 + c2an − 2 + … + ckan − k = 0

解法步骤（特征方程法）：

  1. 写出特征方程： 将 an 替换为 xk， an − 1 替换为 xk − 1，以此类推。 例如对于二阶方程 an − c1an − 1 − c2an − 2 = 0，特征方程为：

    x2 − c1x − c2 = 0

  2. 求特征根： 解出方程的根 r1, r2, …。

  3. 写出通解： 根据根的情况，通解形式如下（以二阶为例）：

    根的情况 通解公式 (A,B 为待定常数)
    两个不相等的实根(r1 ≠ r2) an = A ⋅ r1n + B ⋅ r2n
    两个相等的实根(r1 = r2 = r) an = (A + B ⋅ n) ⋅ rn

  4. 求特解（确定常数）： 代入初始条件（如 a0, a1 的值），解方程组求出 A 和 B。

二、 常系数线性非齐次递推方程

形式： an + c1an − 1 + … = f(n)

（等式右边不是0，而是一个关于 n 的函数）

解法步骤：

通解 = 齐次通解 + 特异解 (an = an(h) + an(p))

  1. 求齐次通解 an(h)： 令右边 f(n) = 0，按照第一部分的方法求出通解。
  2. 求特异解 an(p)： 根据 f(n) 的形式，“猜测”特解的形式并代入原方程求解系数。
  3. f(n) 的形式 猜测特解 an(p) 的形式 注意事项
    多项式 Pk(n) (如 n2 + 1) Qk(n) (同阶多项式，如 An2 + Bn + C) 如果 1 是特征根，需乘n 或 n2
    指数函数 βn (如 3n) C ⋅ βn 如果 β 是特征根，需乘 n (重根乘 n2 )
  4. 组合并求解： 将 an(h) + an(p) 组合，代入初始条件求解常数。

三、 分治递归方程 (Divide and Conquer)

形式： T(n) = aT(n/b) + f(n)

（常用于分析归并排序、二分搜索等算法的时间复杂度）

方法1：主定理 (Master Theorem) —— 最常用

比较 nlogba 与 f(n) 的增长速率：

  1. 情况 1 (根重)： 如果 f(n) = O(nlogba − ϵ) （即 f(n) 增长慢），则： T(n) = Θ(nlogba)
  2. 情况 2 (平衡)： 如果 f(n) = Θ(nlogba) （即同阶），则： T(n) = Θ(nlogbalg n)
  3. 情况 3 (叶重)： 如果 f(n) = Ω(nlogba + ϵ) （即 f(n) 增长快），且满足正则条件，则： T(n) = Θ(f(n))

方法2：递归树法 (Recursion Tree)

当主定理不适用或需要画图分析时使用。

  1. 画出树状结构，每层写出消耗的代价。
  2. 对每一层的代价求和。
  3. 对所有层求总和。

方法3：代换法 (Substitution Method)

  1. 猜测解的形式（如猜测 T(n) = O(nlg n)）。
  2. 使用数学归纳法证明猜测是正确的。

示例：解 an = 5an − 1 − 6an − 2, a0 = 1, a1 = 0

  1. 特征方程： x2 − 5x + 6 = 0
  2. 求根： (x − 2)(x − 3) = 0 ⟹ r1 = 2, r2 = 3
  3. 通解： an = A ⋅ 2n + B ⋅ 3n
  4. 代入初始条件：
    • n = 0 : A + B = 1
    • n = 1 : 2A + 3B = 0
  5. 解方程组： 由(1)得 A = 1 − B，代入(2)： 2(1 − B) + 3B = 0 ⟹ 2 − 2B + 3B = 0 ⟹ B = −2 则 A = 1 − (−2) = 3
  6. 最终解： an = 3 ⋅ 2n − 2 ⋅ 3n

第二章 递归与分治

二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
int binarysearch(int a[ ] ,int x,int n){ 

     int right = n-1,left = 0;
     while(left<=right){
          int mid = (right + left) / 2;
          if(a[mid]==x) return mid;
          if(a[mid]>x) right = mid-1;
          else left = mid+1;
} 
return -1;

}

每执行一次算法的 while 循环，待搜索数组的大小减少一半。 因此，在最坏情况下，while 循环被执行了 O(log n) 次。循环体内运算需要 O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为 O(log n) 。

合并排序

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 辅助函数：合并两个有序子数组
// 将 array[left...mid] 和 array[mid+1...right] 合并
void Merge(int array[], int left, int mid, int right) {
    // 1. 创建临时数组并复制数据
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2]; // 左右临时数组

    for (int i = 0; i < n1; i++) L[i] = array[left + i];
    for (int j = 0; j < n2; j++) R[j] = array[mid + 1 + j];

    // 2. 归并过程
    int i = 0; // L的索引
    int j = 0; // R的索引
    int k = left; // 原数组索引

    while (i < n1 && j < n2) {
        // 比较两边的首元素，取较小的放入原数组
        if (L[i] <= R[j]) {
            array[k] = L[i];
            i++;
        } else {
            array[k] = R[j];
            j++;
        }
        k++;
    }

    // 3. 处理剩余元素
    while (i < n1) { // 如果左边有剩
        array[k] = L[i];
        i++; k++;
    }
    while (j < n2) { // 如果右边有剩
        array[k] = R[j];
        j++; k++;
    }
}

// 主排序函数
void MergeSort(int array[], int left, int right) {
    if (left < right) {
        // 1. 找中间点
        int mid = (left + right) / 2;

        // 2. 递归排序左半部分
        MergeSort(array, left, mid);

        // 3. 递归排序右半部分
        MergeSort(array, mid + 1, right);

        // 4. 合并
        Merge(array, left, mid, right);
    }
}

非递归版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

// 1. 合并函数 (逻辑与递归版完全一样)
// 将 arr[left...mid] 和 arr[mid+1...right] 合并
void Merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
  
    // 创建临时数组
    vector<int> L(n1), R(n2);
  
    for (int i = 0; i < n1; i++) L[i] = arr[left + i];
    for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
  
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
  
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// 2. 非递归合并排序 (主函数)
void MergeSortNonRecursive(vector<int>& arr) {
    int n = arr.size();
    if (n <= 1) return;

    // curr_size 表示当前正在合并的子数组的大小
    // 变化过程：1 -> 2 -> 4 -> 8 ...
    for (int curr_size = 1; curr_size < n; curr_size *= 2) {
  
        // left_start 是每一对子数组的起始位置
        // 每次跳跃 2 * curr_size
        for (int left_start = 0; left_start < n - 1; left_start += 2 * curr_size) {
  
            // 找到中间点，注意不要越界
            int mid = min(left_start + curr_size - 1, n - 1);
  
            // 找到右边界，注意不要越界
            int right_end = min(left_start + 2 * curr_size - 1, n - 1);
  
            // 只有当存在右半部分时才需要合并
            // 如果 mid 已经是最后一个元素，说明没有右半部分，无需操作
            if (mid < right_end) {
                Merge(arr, left_start, mid, right_end);
            }
        }
    }
}

时间复杂度

**T**(**n**)**=**2**T**(**n**/**2**)+**O**(**n**)

使用主定理分析：

a = 2, b = 2, f(n) = n

计算关键指数：

nlogba = nlog22 = n1 = n

由于 f(n) = Θ(nlogba)，符合主定理第二种情况，因此：

T(n) = O(nlog n)

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 核心分区函数：返回基准值的最终索引
int partition(int arr[], int left, int right) {

    // 生成 [left, right] 之间的随机索引
    int randIdx = left + rand() % (right - left + 1);
    swap(arr[left], arr[randIdx]); // C++ 内置 swap 函数

    int pivot = arr[left]; // 1. 选最左边为基准，挖出第一个坑
  
    while (left < right) {
        // 2. 从右向左找比 pivot 小的数
        while (left < right && arr[right] >= pivot) {
            right--; 
        }
        arr[left] = arr[right]; // 填左边的坑，right 变成新坑

        // 3. 从左向右找比 pivot 大的数
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        arr[right] = arr[left]; // 填右边的坑，left 变成新坑
    }
  
    // 4. 基准值填入最后的坑
    arr[left] = pivot;
    return left;
}

//教材写法，交换法
int Partition(int a[], int l, int r) {
           int i = l, j = r+1;
           int x = a[l];
           while (true) {
               while (a[++i] < x && i < r);
               while (a[--j] > x);
               if (i >= j) break;
               Swap(a[i], a[j]);
         }
     a[l] = a[j];
     a[j] = x;
     return j;
}

// 主排序函数
void quicksort(int arr[], int left, int right) {
    //可以加上两步，从左往右扫描数组，如果是升序直接返回，如果是降序，就返回反转后的数组，防止快排陷入最差情况
    //TODO step 1
    //TODO step 2
    if (left < right) {
        // 分区：此时 pivotIdx 位置的元素已经排好了
        int pivotIdx = partition(arr, left, right);
  
        // 递归排序左边
        quicksort(arr, left, pivotIdx - 1);
  
        // 递归排序右边
        quicksort(arr, pivotIdx + 1, right);
    }
}

快速排序（Quick Sort）的时间复杂度分析完全取决于划分（Partition）的质量，也就是基准值（Pivot）选得好不好。

以下是关于最好情况和最坏情况的详细分析：

1. 最好情况 (Best Case)

条件： 每次划分选取的基准值（Pivot）恰好都是当前子数组的中位数。 这意味着每次都能将数组均匀地一分为二，左边一半，右边一半。

分析推导：

  1. 递归结构：这时的递归树是一棵标准的、平衡的二叉树。

  2. 递推公式：

    $$ T(n) = 2T\left(\frac{n}{2}\right) + O(n) $$

    • 2T(n/2)：解决左右两个规模减半的子问题。
    • O(n)：本层划分（Partition）所需的遍历比较时间。

  3. 求解： 根据主定理（Master Theorem）或递归树法：

    • 递归深度为 log2n。
    • 每一层的工作量总和是 O(n)。
    • 总时间 = 层数 × 每层工作量。

结论：

T(n) = O(nlog n)

2. 最坏情况 (Worst Case)

条件： 每次划分选取的基准值都是当前子数组中的最大值或最小值。 这种情况通常发生在：

  1. 数组已经有序（或逆序）。
  2. 并且我们固定选取第一个元素（或最后一个）作为基准值。

分析推导：

  1. 划分极度不平衡： 比如数组 [1, 2, 3, 4, 5]，选 1 做基准。

    • 左边子数组长度：0
    • 右边子数组长度：n − 1
    • 这导致递归树退化成了一个链表（斜树）。

  2. 递推公式：

    T(n) = T(n − 1) + T(0) + O(n) = T(n − 1) + O(n)

    • T(n − 1)：只解决了一个规模减少 1 的子问题。
    • O(n)：本层划分的时间。

  3. 求解（等差数列求和）：

    $$ \begin{aligned} T(n) &= n + (n-1) + (n-2) + \dots + 1 \\ &= \frac{n(n+1)}{2} \\ &\approx \frac{n^2}{2} \end{aligned} $$

结论：

T(n) = O(n2)

3. 总结对比图表

情况 发生条件 递归树形态 递推公式 时间复杂度
最好情况 每次选到中位数 平衡二叉树 T(n) = 2T(n/2) + n O(nlog n)
最坏情况 每次选到极值 (有序数组) 线性链表 (斜树) T(n) = T(n − 1) + n O(n2)
平均情况 随机选取基准 近似平衡 N/A O(nlog n)

4. 如何避免最坏情况？

这就回到了我们之前讨论的代码优化：

  • 随机化 (Randomization)：在 Partition 之前，随机选一个数与 left 交换。这样即使原数组有序，也能打破其顺序，将期望复杂度稳定在 O(nlog n)。
  • 三数取中 (Median of Three)：取头、中、尾三个数的中位数作为基准，也能有效避免有序数组带来的 O(n2) 问题。

线性时间选择

找出第k小的元素

随机化选择

1
2
3
4
5
6
7
8
9
int RandomizedSelect(int a[], int l, int r, int k) {
    if (l == r) return a[l];
    int i = RandomizedPartition(a, l, r); // 使用随机基准划分
    int j = i - l + 1; // 计算基准是第几小
    if (k <= j) 
        return RandomizedSelect(a, l, i, k);
    else 
        return RandomizedSelect(a, i + 1, r, k - j);
}

线性时间选择：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int Select(int a[], int l, int r, int k) {
    if (r - l < 75) {
        // 小规模数据直接用某个简单算法排序返回
        // insertSort(a, l, r); 
        return a[l + k - 1];
    }

    // 1. 分组：每5个一组，找中位数，换到数组前部
    for (int i = 0; i <= (r - l - 4) / 5; i++) {
        int s = l + 5 * i;
        int t = s + 4;
        for (int j = 0; j < 3; j++) bubble(s, t - j); // 简单排序找中位数
        swap(a[l + i], a[s + 2]); // 第3小即中位数换到 a[l+i]
    }

    // 2. 递归找到“中位数的中位数” x
    int x = Select(a, l, l + (r - l - 4) / 5, (r - l - 4) / 10 + 1);

    // 3. 以 x 为基准进行划分
    int i = Partition(a, l, r, x); 
    int j = i - l + 1;

    // 4. 判断 k 落在哪个区间
    if (k <= j) return Select(a, l, i, k);
    else return Select(a, i + 1, r, k - j);
}

时间复杂度分析

证明 x 至少比 $\frac{3n}{10} - 1$ 个元素大

  • 第一步：分组与中位数 我们将 n 个元素分成 m = ⌈n/5⌉ 组。在这些组的中位数里，递归找到它们的中位数 x。根据中位数的定义，至少有 m/2 个组的中位数是  ≤ x 的。
  • 第二步：计算“确定比 x 小”的元素 除去 x 所在的组，至少有 m/2 − 1 个组，它们的中位数都小于 x。 在每一个这样的组中，由于组内 5 个元素已经排过序，中位数小于 x，那么该组内比中位数小的 2 个元素 也一定小于 x。 加上中位数本身，每组至少有 3 个元素 小于 x。
  • 第三步：求和
    • 这些组贡献了：$3 \times (\frac{m}{2} - 1)$ 个元素。
    • 将 m ≈ n/5 代入：$3 \times (\frac{n/5}{2} - 1) = \frac{3n}{10} - 3$。
    • 再加上 x 所在的组里，至少还有 2 个元素 比 x 小。
    • 最终结果 ：$(\frac{3n}{10} - 3) + 2 = \frac{3n}{10} - 1$。

BFPTR 的时间复杂度递推公式为：

$$ T(n) \le T(\frac{n}{5}) + T(\frac{7n}{10}) + O(n) $$

  • T(n/5) 是找中位数的中位数。
  • T(7n/10) 是最坏情况下，剩下需要处理的元素（即 $n - \frac{3n}{10} = \frac{7n}{10}$）。
  • 由于 $\frac{1}{5} + \frac{7}{10} = \frac{9}{10} < 1$，根据主定理或递推分析，该算法可以保证在 O(n) 内完成。

教材中采用

$$ T(n) \le T(\frac{n}{5}) + T(\frac{3n}{4}) + O(n) $$

因为0.7约等于0.75，3/4更好算

在 n 较小时，递归寻找“中位数的中位数”带来的开销（如函数调用栈、数组切片等）会超过直接排序。

  1. 数学上的正值要求 ：在证明 T(n) ≤ cn 时，我们需要保证 $\frac{3n}{10} - 6 > 0$（即 n > 20）。
  2. 工程经验值 ：当 n 达到 75 左右时，$\frac{3n}{10}$ 带来的“理想基准值”优势才开始显著大于递归本身的损耗。
  3. 效率平衡 ：对于小于 75 的数组，插入排序的常数项非常小，速度极快。强行递归反而会变慢。

动态规划

矩阵连乘

1.定义最优解

假设矩阵连乘积 AiAi + 1…Aj 的一个 最优计算次序 （即乘法次数最少的方案）在矩阵 Ak 和 Ak + 1 之间将矩阵链断开。

那么，这个最优方案的总代价可以表示为：

m[i][j] = m[i][k] + m[k + 1][j] + pi − 1pkpj

其中：

  • m[i][k] 是左子链 Ai…Ak 的计算代价。
  • m[k + 1][j] 是右子链 Ak + 1…Aj 的计算代价。
  • pi − 1pkpj 是最后这两部分结果相乘的代价。

2. 核心证明：反证法

我们要证明： 如果原问题是最优的，那么它的子问题（左子链和右子链）也必须是最优的。

证明过程：

  1. 假设子问题不是最优的： 假设对于左子链 Ai…Ak，存在另一种计算次序，其代价 m′[i][k] 比我们当前方案中的 m[i][k] 还要小（即 m′[i][k] < m[i][k]）。

  2. 进行“剪切与粘贴”： 我们把原方案中的左子链计算部分“剪掉”，换成这个更优的方案（“粘贴”进来）。

  3. 推导矛盾： 替换后的总代价 M 将变为：

    M = m′[i][k] + m[k + 1][j] + pi − 1pkpj

    由于 m′[i][k] < m[i][k]，显然有：

    M < m[i][j]

  4. 结论： 这意味着我们找到了一个比“最优解”代价更小的方案。这与我们最初假设“m[i][j] 是最优解”相 矛盾 。

因此，原问题的最优解所包含的子问题的解也必须是最优的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * MatrixChain: 计算最优乘法次数
 * dims: 维度数组 (p)，长度为 n+1
 * n: 矩阵的个数
 * cost: 存储最小乘法次数的表 (m)
 * bestSplit: 存储最优切分点的表 (s)
 */
void MatrixChain(int *dims, int n, int **cost, int **bestSplit) {
    // 1. 初始化：单个矩阵相乘次数为 0
    for (int i = 1; i <= n; i++) {
        cost[i][i] = 0;
    }

    // 2. len 表示当前处理的链条长度（从长度 2 到 n）
    for (int len = 2; len <= n; len++) {
  
        // 3. start 表示链条的起点
        for (int start = 1; start <= n - len + 1; start++) {
  
            // 4. end 表示链条的终点
            int end = start + len - 1;

            // 先假设在第一个可能的位置切开，算出初始代价
            // 相当于在第 start 个矩阵后面切一刀
            cost[start][end] = cost[start][start] + cost[start + 1][end] 
                               + dims[start - 1] * dims[start] * dims[end];
            bestSplit[start][end] = start;

            // 5. split 表示尝试不同的切分位置 k
            for (int split = start + 1; split < end; split++) {
  
                // 计算公式：左边代价 + 右边代价 + 合并代价
                int t = cost[start][split] + cost[split + 1][end] 
                        + dims[start - 1] * dims[split] * dims[end];

                // 如果发现更省力的切法，就更新它
                if (t < cost[start][end]) {
                    cost[start][end] = t;
                    bestSplit[start][end] = split; // 记录这个最好的切分位置
                }
            }
        }
    }
}

/**
 * Traceback: 打印具体的加括号方式
 */
void Traceback(int start, int end, int **bestSplit) {
    if (start == end) {
        cout << "A" << start;
        return;
    }
  
    cout << "(";
    // 递归打印左半部分
    Traceback(start, bestSplit[start][end], bestSplit);
  
    // 递归打印右半部分
    Traceback(bestSplit[start][end] + 1, end, bestSplit);
    cout << ")";
}

状态方程

$$ m[i, j] = \begin{cases} 0 & \text{if } i = j \\ \min_{i \leq k < j} \{ m[i, k] + m[k+1, j] + p_{i-1}p_k p_j \} & \text{if } i < j \end{cases} $$

最长公共子序列

最优子结构证明

假设有两个序列：

  • X = {x1, x2, …, xm}
  • Y = {y1, y2, …, yn}
  • 令 Z = {z1, z2, …, zk} 是它们的 任意一个 LCS 。

我们将序列的“前缀”记为 Xi = {x1, …, xi}。

  1. 定理陈述：LCS 的最优子结构

LCS 的最优子结构性质可以分三种情况讨论：

  1. 情况 1：若 xm = yn 则 zk = xm = yn，且 Zk − 1 是 Xm − 1 和 Yn − 1 的一个 LCS。
  2. 情况 2：若 xm ≠ yn 且 zk ≠ xm 则 Z 是 Xm − 1 和 Y 的一个 LCS。
  3. 情况 3：若 xm ≠ yn 且 zk ≠ yn 则 Z 是 X 和 Yn − 1 的一个 LCS。
  1. 证明过程

情况 1 的证明（末尾相等）：

  • 已知 ：xm = yn。
  • 假设 ：zk ≠ xm。那么我们可以在 Z 的末尾加上 xm，得到一个长度为 k + 1 的公共子序列。这与 Z 是长度为 k 的“最长”公共子序列相 矛盾 。所以必有 zk = xm = yn。
  • 子问题证明 ：现在我们要证 Zk − 1 是 Xm − 1 和 Yn − 1 的 LCS。
  • 使用 反证法 ：若存在一个更长的公共子序列 W，其长度大于 k − 1。
  • 那么把 xm 加到 W 的末尾，就会得到一个长度大于 k 的 X 和 Y 的公共子序列。
  • 这与 Z 的长度为 k 是最优解矛盾。

情况 2 和 3 的证明（末尾不等）：

以情况 2为例（xm ≠ yn 且 zk ≠ xm）：

  • 分析 ：既然 zk ≠ xm，说明 X 的最后一个元素 xm 并没有参与构成当前的 LCS。
  • 结论 ：因此，Z 必然也是 Xm − 1 和 Y 的一个公共子序列。
  • 子问题证明 ：若 Xm − 1 和 Y 存在一个比 Z 更长的公共子序列 W（长度  > k），那么 W 显然也是 X 和 Y 的公共子序列。
  • 这同样与 Z 是 X 和 Y 的最优解（长度为 k）矛盾。

状态转移方程

$$ dp[i][j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0 \\ dp[i-1][j-1] + 1 & \text{if } X[i] = Y[j] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{if } X[i] \neq Y[j] \end{cases} $$

  • 相等时 (X[i] =  = Y[j]) ：说明发现了一个公共字符。当前长度 = 左上角格子的长度 + 1。
  • 不相等时 (X[i] ≠ Y[j]) ：说明当前字符对不上。我们要继承之前的“遗产”，看“去掉X当前字符”和“去掉Y当前字符”哪个留下的子序列更长，取最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * m: 序列 x 的长度
 * n: 序列 y 的长度
 * x, y: 待比较的两个字符串（通常下标从 1 开始）
 * c: 长度表，c[i][j] 表示 LCS 的长度
 * b: 方向表，记录回溯路径
 */
int LCSLength(int m, int n, char *x, char *y, int **c, int **b) {
    int i, j;

    // 初始化：如果其中一个序列为空，则 LCS 长度为 0
    for (i = 0; i <= m; i++) c[i][0] = 0; // 第一列置 0
    for (i = 0; i <= n; i++) c[0][i] = 0; // 第一行置 0

    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            // 情况 1：当前字符相等，找到一个公共字符
            if (x[i] == y[j]) { 
                c[i][j] = c[i - 1][j - 1] + 1; // 长度在左上方基础上 +1
                b[i][j] = 1;                  // 记录方向为：左上方（对角线）
            } 
            // 情况 2：字符不等，且“上方”的 LCS 更长
            else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];         // 继承上方的长度
                b[i][j] = 2;                  // 记录方向为：上方
            } 
            // 情况 3：字符不等，且“左方”的 LCS 更长
            else {
                c[i][j] = c[i][j - 1];         // 继承左方的长度
                b[i][j] = 3;                  // 记录方向为：左方
            }
        }
    }
    return c[m][n]; // 返回最终的最长公共子序列长度
}
/**
 * i, j: 当前回溯到的位置（初始调用通常为 m, n）
 * x: 序列 x
 * b: 方向表
 */
void LCS(int i, int j, char *x, int **b) {
    // 递归边界：如果回溯到序列开头，结束
    if (i == 0 || j == 0) return;

    if (b[i][j] == 1) {
        // 方向 1：说明 x[i] 是 LCS 的一部分
        LCS(i - 1, j - 1, x, b); // 先递归前面的部分
        cout << x[i];            // 后序打印，保证字符顺序正确
    } 
    else if (b[i][j] == 2) {
        // 方向 2：来自上方，向上移动一行继续找
        LCS(i - 1, j, x, b);
    } 
    else {
        // 方向 3：来自左方，向左移动一列继续找
        LCS(i, j - 1, x, b);
    }
}

时间复杂度 : O(m × n)

  • 双重循环填表耗时 m × n。
  • 回溯过程最多走 m + n 步。

根据最长公共子序列求解最长递减子序列

将原来的数组降序排序，与原数组进行最长公共子序列算法可得。

sorted_arr=sorted(arr, reverse=True)

最大字段和

1.定理陈述

若 dp[i] 是以 ai 结尾的所有子段中和最大的那一个，则它必然包含以 ai − 1 结尾的最大子段和 dp[i − 1]（前提是 dp[i − 1] > 0）。

2. 证明过程（反证法 / 剪切粘贴法）

第一步：定义结构

以 ai 结尾的子段只有两种可能：

  1. 单独一个元素 ：即 [ai]。
  2. 与前面相连 ：即 [astart, …, ai − 1, ai]。此时，dp[i] = (以 ai − 1 结尾的某个子段) + ai。

第二步：假设与矛盾推导

假设第 2 种情况是我们要的最优解（即 dp[i] 的和最大），但它所包含的子问题解——“以 ai − 1 结尾的子段”——不是最优的。

  1. 假设 ：存在另一个以 ai − 1 结尾的子段，其和为 dp′[i − 1]，且 dp′[i − 1] > dp[i − 1]。
  2. 剪切与粘贴 ：我们将原方案中以 ai − 1 结尾的部分“剪掉”，换成这个更优的 dp′[i − 1]。
  3. 得到新解 ：新的总和 M = dp′[i − 1] + ai。
  4. 推导矛盾 ：由于 dp′[i − 1] > dp[i − 1]，显然 M > dp[i − 1] + ai。这说明原来的 dp[i] 根本不是以 ai 结尾的最大子段和。

结论 ：这与前提矛盾。因此，以 ai** 结尾的最优解，必然包含了以 ai − 1 结尾的最优解。**

3. 状态转移方程

基于以上最优子结构性质，我们可以得出最大子段和的递归式：

dp[i] = max (dp[i − 1] + ai, ai)

  • 如果 dp[i − 1] > 0**** ：加上前面的子段会对当前更有利，所以“拖家带口”一起走。
  • 如果 dp[i − 1] ≤ 0**** ：前面的子段是“负资产”，不如断舍离，从 ai 重新开始。

4. 最终答案的获取

注意，dp[i] 仅仅是以 i 结尾的最优解。整个数组的最大子段和应该是所有这些 dp[i] 中的最大值：

Result = max1 ≤ i ≤ n{dp[i]}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int MaxSubSum(int n, int a[]) {
    int sum = 0, b = 0;
    for (int i = 0; i < n; i++) {
        if (b > 0) b += a[i]; // 如果前面的贡献是正的，就加上
        else b = a[i];        // 否则，从当前元素重新开始
        if (b > sum) sum = b; // 更新全局最大值
    }
    return sum;
}

/**
 * a: 输入数组
 * n: 数组长度
 * bestStart: 传引用，返回起点的下标
 * bestEnd: 传引用，返回终点的下标
 */
int MaxSubSumWithIndices(int a[], int n, int &bestStart, int &bestEnd) {
    int maxSum = -100000; // 初始为一个极小值
    int currentSum = 0;
    int tempStart = 0;    // 临时起点的记录员

    for (int i = 0; i < n; i++) {
        // 动态规划部分
        if (currentSum > 0) {
            currentSum += a[i];
        } else {
            // 前面的贡献是负的，舍弃之，从当前位置开始新的一段
            currentSum = a[i];
            tempStart = i; 
        }

        // 更新全局最优解
        if (currentSum > maxSum) {
            maxSum = currentSum;
            bestStart = tempStart; // 此时的临时起点变成真正的起点
            bestEnd = i;           // 当前位置就是终点
        }
    }
    return maxSum;
}

时间复杂度：O(N)

0/1背包

证明（反证法）：

假设我们已经找到了容量为 C 时的最优选法，其中包含了物品 i。

那么，如果我们将物品 i 从背包中拿走，剩下的物品对于剩余容量 C − wi 来说，也必须是最优的。

  • 如果不是最优的： 意味着在容量 C − wi 下，存在另一种选法价值更高。
  • 那么： 我们把这组更好的选法放进背包，再加上物品 i，就会得到一个比“最优解”总价值更高的方案。
  • 结论： 这产生了矛盾，因此子问题的解也必须是最优的。

0/1 背包问题最优解的递归方程式

设：

  • dp[i][j] 表示在前 i 个物品中进行选择，且背包容量为 j 时的最大总价值。
  • Wi 表示第 i 个物品的重量（注意：若物品编号从1开始，则对应 Wi；若代码中数组从0开始，通常对应 Wi − 1）。
  • Vi 表示第 i 个物品的价值。

递归方程式（状态转移方程）如下：

$$ dp[i][j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0 \quad (\text{边界条件}) \\ dp[i-1][j] & \text{if } j < W_i \quad (\text{当前背包装不下第 } i \text{ 个物品}) \\ \max \{ dp[i-1][j], \quad dp[i-1][j - W_i] + V_i \} & \text{if } j \ge W_i \quad (\text{能装下，决策：选或不选}) \end{cases} $$

（2）算法伪代码描述

该算法分为两步：

  1. 填表 ：计算最大价值。
  2. 回溯 ：根据表格反推选了哪些物品。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * v: 价值数组 (values)
 * w: 重量数组 (weights)
 * c: 背包总容量 (capacity)
 * n: 物品数量
 * m: 动态规划表，m[i][j] 表示在前 i 个物品中，容量为 j 时的最大价值
 */
int Knapsack(int *v, int *w, int c, int n, int **m) {
    // 1. 初始化：只考虑最后一个物品 n (即第 n 个物品的决策)
    int jMax = min(w[n] - 1, c); 
    for (int j = 0; j <= jMax; j++) {
        m[0][j] = 0; // 容量不够装第 n 个物品
    }
    for (int j = w[n]; j <= c; j++) {
        m[0][j] = v[n]; // 容量够装，价值为 v[n]
    }

    // 2. 迭代计算：处理剩余的物品 (从 1 到 n-1)
    for (int i = 1; i <= n - 1; i++) {
        // 情况 A：容量 j 不足以装下当前物品 i
        int jMax = min(w[i] - 1, c); 
        for (int j = 0; j <= jMax; j++) {
            m[i][j] = m[i - 1][j]; // 只能继承前一个状态
        }
        // 情况 B：容量 j 足够装下物品 i
        for (int j = w[i]; j <= c; j++) {
            // 决策：不放物品 i (m[i-1][j]) VS 放物品 i (m[i-1][j-w[i]] + v[i])
            m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + v[i]);
        }
    }
  
    // 注意：根据循环逻辑，最终最大价值存储在 m[n-1][c]
    return m[n-1][c]; 
}

/**
 * m: 填好的 DP 表
 * w: 重量数组
 * c: 背包剩余容量
 * n: 物品数量
 * x: 结果数组，x[i]=1 表示选中，0 表示未选
 */
void Traceback(int **m, int *w, int c, int n, int *x) {
    for (int i = n - 1; i >= 1; i--) {
        // 如果当前总价值等于“不放该物品”时的价值，说明没选它
        if (m[i][c] == m[i - 1][c]) {
            x[i] = 0;
        } else {
            // 否则，说明选了物品 i，并减去其重量
            x[i] = 1;
            c -= w[i];
        }
    }
    // 处理最后一个物品（在 DP 表中对应的第 0 行）
    x[0] = (m[0][c] > 0) ? 1 : 0;
}

（3）算法时间复杂度分析

对上述算法进行分析：

  1. 填表过程 ：
  • 算法使用了两层嵌套循环。
  • 外层循环遍历物品数量 i，从 1 到 n，执行 n 次。
  • 内层循环遍历背包容量 j，从 1 到 C，执行 C 次。
  • 循环体内部的操作（比较、加法、赋值）都是常数时间操作 O(1)。
  • 因此，填表的时间复杂度为 O(n × C) 。
  1. 回溯过程 ：
  • 循环从 n 递减到 1，执行 n 次。
  • 内部操作为常数时间。
  • 这部分的时间复杂度为 O(n)。

总时间复杂度：

T(n) = O(n × C) + O(n) ≈ O(n × C)

注意：

这里的 C 是背包的容量数值，而不是输入的规模。如果 C 非常大（例如 C = 2n），该算法的效率会变得很低。因此，严谨地说，这是一个 伪多项式时间（Pseudo-polynomial time) 算法。

贪心算法

活动安排

算法伪代码及复杂度分析

核心思路：

为了安排尽可能多的活动，我们应该总是选择结束时间最早且与当前已选活动不冲突的活动。这样可以为剩下的时间段留出最大的空间，从而容纳更多的活动。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 贪心算法求解活动安排问题
 * * 参数说明:
 * n   : 活动的总数量
 * s[] : 活动开始时间数组 (下标从1开始, s[1]...s[n])
 * f[] : 活动结束时间数组 (下标从1开始, f[1]...f[n])
 * ***重要前提***: f[] 必须已经按照非递减顺序(从小到大)排好序
 * A[] : 布尔数组，用于记录结果。A[i] = true 表示选中第 i 个活动
 */
void GreedySelector(int n, Type s[], Type f[], bool A[])
{
    // 步骤 1: 贪心选择策略 - 总是先选择结束时间最早的第一个活动
    // 因为 f[] 已排序，所以 f[1] 是结束最早的
    A[1] = true; 
  
    int j = 1; // j 用于记录“上一个被选中的活动”的索引

    // 步骤 2: 依次检查剩余的 n-1 个活动
    for (int i = 2; i <= n; i++) {
        // 检查相容性:
        // 如果当前活动 i 的开始时间 (s[i]) 晚于或等于
        // 上一个被选活动 j 的结束时间 (f[j])
        if (s[i] >= f[j]) { 
            A[i] = true;  // 标记选中
            j = i;        // 更新 j，将当前活动 i 设为“最近选中的活动”
        }
        else {
            A[i] = false; // 时间冲突，不选中
        }
    }
}

对该函数的复杂度分析如下：

  • 循环次数 ：代码中只有一个 for 循环，循环变量 i 从 2 遍历到 n。这意味着循环体总共执行了 n − 1 次。
  • 循环内部操作 ：在循环体内，执行的是简单的比较 (>=) 和赋值操作。这些都是常数时间操作，记为 O(1)。
  • 总运算量 ：(n − 1) × O(1)。

结论：

该函数本身的时间复杂度为 O(n)（线性时间复杂度）。

说明算法采用的贪心策略

该算法采用的贪心策略是： 最早结束时间优先 (Earliest Finish Time First) 。

解释：

在所有与当前已选活动相容（不冲突）的剩余活动中，总是选择结束时间最早的那个活动。

  • 理由： 结束时间越早，剩余的可安排时间资源就越多，从而更有可能容纳后续的活动。这是一种“目光短浅”但在此问题中能导致全局最优的策略。

贪心选择性质的证明（以“替换法”证明）

这一步的目的是证明：全局最优解中，一定可以包含贪心选择出来的那个局部最优项。

  • 设定前提 ：设 E = {1, 2, …, n} 是按结束时间 fi 非减序排列的活动集合，其中活动 1 具有最早结束时间。
  • 假设最优解 ：设 A ⊆ E 是该问题的一个最优解，且 A 中的第一个活动是 k。
  • 分类讨论 ：
  1. 如果 k = 1**** ：说明最优解 A 已经包含了贪心选择的活动 1，证明结束。
  2. 如果 k > 1**** ：说明最优解没有选活动 1，而是选了 k。此时我们构造一个新的集合 B = (A − {k}) ∪ {1}，即 用活动 1 替换掉活动 k**** 。
  • 证明可行性 ：因为活动 1 的结束时间 f1 ≤ fk（因为集合是按结束时间排序的），而 k 与 A 中后续活动是不冲突的，那么结束得更早的活动 1 自然也不会与后续活动冲突。
  • 结论 ：由于 B 中的活动数量和 A 一样多，且 B 也是相容的，所以 B 也是一个最优解。这证明了 总存在一个包含贪心选择（活动 1）的最优解 。

最优子结构性质（以“反证法”证明）

这一步的目的是证明：做出贪心选择后，原问题的最优解包含了子问题的最优解。

简化问题 ：当我们选择了活动 1 后，剩下的可选活动集合变为 E′ = {i ∈ E : si ≥ f1}（即所有开始时间晚于活动 1 结束时间的活动）。 反证逻辑 ：

  • 设 A 是原问题 E 的最优解，则 A′ = A − {1} 应该是子问题 E′ 的最优解。
  • 假设 A′** 不是 E′ 的最优解** ：那么一定存在另一个解 B′，它包含的活动数量比 A′ 更多。
  • 推导矛盾 ：如果我们把活动 1 加回到 B′ 中，得到 B = B′ ∪ {1}。由于 B′ 活动更多，那么 B 的活动数量就会比原始最优解 A 还要多。
  • 结论 ：这与“A 是最优解”的前提矛盾。因此，每一步贪心选择所留下的子问题，其最优解与贪心选择合并后，一定是原问题的最优解。

单源最短路径

形式化描述

对图G(V, E), 源点v，从三方面描述问题

  • 源点 v，图中顶点集合 V, 各顶点 u ∈ V 的全局最短路径及其长度 d(v, u)
    • 算法迭代过程中保持不变
  • 用于构造最短路径的当前顶点集合 Si，
    • 不断增加，定义了不同规模的子问题
  • 指标：相对于现有 Si，对各顶点 u ∈ V，dist[u]
    • 随着 Si 的变化，dist[u]可能需要不断更新

问题/子问题描述： [Si, { < u, dist[u] > }]， Si ⊆ V， u ∈ V

  • 最简子问题： [{u}, { < u, 0 > }]， Si只包含源点u
  • 原问题： [V, { < u, dist[u] > }] = [V, { < u, d(u, v) > }]， Si = V

贪心选择性质的证明 (图 4-6)

1766578742560

这一部分是为了证明：为什么每次从“未确定集合”中挑选 dist** 值最小的顶点 u，这个 dist[u] 就一定是源点到 u 的最短路径距离？**

证明思路：反证法

  1. 假设： 存在一条从源点 v 到 u 的路径，其长度比当前的 dist[u] 还要短。
  2. 寻找矛盾点：
    • 如图 4-6 所示，这条假设的“更短路径”必然会离开已确定集合 S。
    • 设 x 是这条路径上离开 S 后的第一个顶点。
    • 那么，从源点 v 到 x 的路径长度为 d(v, x)。因为 x 在 S 之外，且它是路径上的一个中间点，根据边权非负的原则，到达 x 的距离 dist[x] 必然满足： dist[x] ≤ d(v, x) ≤ 假设的 u 的路径长度 < dist[u]
  3. 结论： * 如果 dist[x] < dist[u]，那么按照 Dijkstra 算法的贪心策略，算法应该先选择顶点 x 加入 S，而不是先选择 u。
    • 这与“算法当前选择了 u”相矛盾。
    • 因此，不存在更短的路径，dist[u] 就是最短路径长度。

最优子结构性质的证明 (图 4-7)

1766578757348

这一部分是为了证明：当我们将顶点 u** 加入集合 S 后，更新其他顶点 i 的 dist 值时，为什么只需要考虑经过 u 的直接边？**

证明逻辑：

当 u 加入 S 后，可能会产生新的通往顶点 i 的特殊路径（特殊路径指：除了终点 i 外，其他点都在 S 中的路径）。

  1. 直接路径： 路径为 v → … → u → i。其长度为 dist[u] + c[u][i]。如果这个值比原来的 dist[i] 小，我们就更新它。
  2. 间接路径 (图 4-7)： 如果新路径是经过 u 后，又回到了 S 中的某个老顶点 x，最后再到达 i。
    • 分析： 因为顶点 x 是“老 S”中的成员，它比 u 更早加入 S。
    • 根据算法逻辑，源点到 x 的最短距离在 u 加入之前就已经确定了。
    • 结论： 经过 u 再绕回 x 的路径长度，必然大于源点直接到 x 的长度。因此，这种“绕路”的情况不需要考虑。

总结： 每次加入新点 u 后，只需要通过 u 对其相邻的、不在 S 中的顶点进行一次“松弛操作”（Relaxation）即可。

代码实现

  1. 选离原点最近且未访问的点
  2. 标记该点访问过
  3. 更新所有未访问结点到原点距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

/*
 * Dijkstra 核心算法
 * 参数:
 * n: 顶点数
 * v: 源点
 * dist[]: 距离数组 (输出)
 * prev[]: 前驱数组 (输出)
 * c[][]: 邻接矩阵 (输入)
 * m是整形最大值
 */

void Dijkstra(int n, int v, int dist[], int prev[], int c[][])
{
    bool s[n + 1]; // 集合 S，s[i]=true 表示点 i 的最短路径已确定

    // --- 步骤 1: 初始化 (Initialization) ---
    for (int i = 1; i <= n; i++)
    {
        dist[i] = c[v][i]; // 初始距离为源点直连的距离
        s[i] = false;      // 所有点初始都不在集合 S 中

        // 设置前驱节点
        if (dist[i] == M) {
            prev[i] = 0; // 如果不可达，前驱置空
        }
        else {
            prev[i] = v; // 如果可达，前驱就是源点 v
        }
    }

    dist[v] = 0; // 源点到自己的距离为 0
    s[v] = true; // 将源点加入集合 S

    // --- 步骤 2: 循环 n-1 次，确定剩余 n-1 个点的最短路径 ---
    for (int i = 1; i < n; i++)
    {
        int temp = M;
        int u = v; 

        // A. 贪心选择 (Selection)
        // 在未被访问的点 (V-S) 中，寻找距离源点最近的点 u
        for (int j = 1; j <= n; j++)
        {
            if ((!s[j]) && (dist[j] < temp))
            {
                u = j;
                temp = dist[j];
            }
        }
  
        // 如果找不到更近的点（说明剩下的点都不可达），提前结束
        if (temp == M) break; 

        s[u] = true; // 将点 u 加入集合 S，表示它的最短路径已彻底确定

        // B. 松弛更新 (Relaxation)
        // 借道 u，看能否缩短源点到其他未访问点 j 的距离
        for (int j = 1; j <= n; j++)
        {
            // 条件：j 不在 S 中，且 u 到 j 有边
            if ((!s[j]) && (c[u][j] < M))
            {
                int newdist = dist[u] + c[u][j]; // 计算经过 u 到达 j 的新距离
  
                // 如果新距离比原来的 dist[j] 更短，则更新
                if (newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u; // 关键：记录 j 的前驱是 u，用于回溯路径
                }
            }
        }
    }
}

/*
 * 递归输出路径
 * 原理：利用 prev 数组不断找前驱，直到回溯到源点，利用递归栈反向打印
 */
void Traceback(int v, int i, int prev[])
{
    // 递归终止条件：找到了源点
    if (v == i)
    {
        cout << i;//打印原点
        return;
    }
  
    // 递归调用：先打印前面的路径
    Traceback(v, prev[i], prev);
  
    // 再打印当前点
    cout << "->" << i;
}

T(n) = O(n) + (n − 1) × [O(n) + O(n)] = O(n2)

  • 最终复杂度： O(n2)
  • 空间复杂度： O(n2)（因为使用了邻接矩阵 c[n+1][n+1]）

分数背包问题

贪心选择性质证明（证明“第一步”拿单位价值最高的是对的）

我们使用 替换法（Substitution） 来证明，这种方法在你提供的最优装载问题证明中也有体现。

  • 设定前提 ：设物品已按单位价值从大到小排序，即 $\frac{v_1}{w_1} \ge \frac{v_2}{w_2} \ge \dots \ge \frac{v_n}{w_n}$。
  • 假设最优解 ：设 A = {x1, x2, …, xn} 是一个最优解，其中 xi 是物品 i 装入的比例（0 ≤ xi ≤ 1）。
  • 比较贪心解 ：贪心算法会尽可能多地装入物品 1。如果 A 中 x1 < 1 且背包还有空间，或者 x1 不是在当前限制下的最大比例，那么 A 就没有完全遵循贪心策略。
  • 构造新解 ：
  1. 如果在 A 中物品 1 没有装满，我们可以从 A 中剔除一部分单位价值较低的物品 j（其中 j > 1），换成相同重量的物品 1。
  2. 设换入的重量为 Δw。
  • 证明价值增加 ：
  • 原价值减少了 $\Delta w \cdot \frac{v_j}{w_j}$，新价值增加了 $\Delta w \cdot \frac{v_1}{w_1}$。
  • 因为 $\frac{v_1}{w_1} \ge \frac{v_j}{w_j}$，所以总价值 ∑vixi 必然不会减少。
  • 结论 ：这说明总存在一个包含“尽可能多地装入单位价值最高物品”的最优解。

最优子结构性质证明（证明“剩下的”部分依然是最优的）

这一步利用 反证法 ，证明原问题的最优解包含子问题的最优解，逻辑与你图片中的 Step 2 一致。

  • 简化问题 ：假设我们已经根据贪心选择，装入了重量为 w 的物品 1。此时，剩余的背包容量为 C′ = C − w，剩余物品集合为 E′ = {2, 3, …, n}。
  • 反证逻辑 ：
  • 设 S 是原问题的最优解。那么 S 去掉物品 1 后的部分 S′，必须是子问题（容量 C′，集合 E′）的最优解。
  • 假设 S′** 不是子问题的最优解** ：意味着存在另一个方案 S″，在容量 C′ 下能获得比 S′ 更高的价值。
  • 推导矛盾 ：如果我们把物品 1 加回到 S″ 中，得到的新解总价值将超过 S。这与“S 是原问题的最优解”矛盾。
  • 结论 ：每一步贪心选择后，剩下的问题依然满足最优子结构，可以递归地使用贪心策略。

贪心解决的是分数背包，对于0/1背包不行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void Knapsack(int n, float M, float v[], float w[], float x[]) {
    // 关键步骤：必须按照“单位价值” (v/w) 从大到小排序
    // 注意：这里的 v[] 和 w[] 必须同步交换顺序
    Sort(n, v, w); 

    int i;
    // 初始化：将所有物品的选择比例置为 0
    for (i = 1; i <= n; i++) x[i] = 0;

    float c = M; // c 代表当前背包的剩余容量 (Current Capacity)

    // 循环：依次考察排序后的物品
    for (i = 1; i <= n; i++) {
        // 如果当前物品 i 的重量大于剩余容量 c，说明装不下了，跳出循环
        if (w[i] > c) break;
  
        // 否则，将物品 i 全部装入
        x[i] = 1;
  
        // 更新剩余容量
        c -= w[i];
    }

    // 处理“跳出循环”时的那个物品（即只能装一部分的物品）
    // 如果 i <= n，说明是 break 出来的，或者是刚好处在最后一个
    if (i <= n)
        x[i] = c / w[i]; // 装入比例 = 剩余容量 / 物品总重量
}

时间复杂度分析

  1. 排序 (Sort)： 这是算法中最耗时的部分。使用高效排序（如快排、归并），时间复杂度为 O(nlog n)。
  2. 循环 (for)： 代码中只有一个从 1 到 n 的循环，最坏情况遍历所有物品，时间复杂度为 O(n)。

总时间复杂度：

T(n) = O(nlog n) + O(n) = O(nlog n)

最优装载问题

最优装载问题（Optimal Loading Problem） 是贪心算法中最经典、最直观的案例之一。虽然它看起来像背包问题，但它的目标略有不同，因此解法也更加简单。

以下是关于该问题的详细描述和贪心策略。

问题描述 (Problem Description)

1. 场景设定

假设有一艘轮船（或者一辆卡车），它的最大载重量为 C。

码头上有 n 个集装箱（古董、货物），第 i 个集装箱的重量为 wi。

注意 ：与背包问题不同的是，这些集装箱 没有“价值”的区别 （或者说每个集装箱的价值都视为 1）。

2. 目标

我们的目标是在不超过轮船载重量 C 的前提下， 装入尽可能多的集装箱数量 。

3. 数学形式化

设 xi 为变量，当 xi = 1 时表示装入第 i 个集装箱，当 xi = 0 时表示不装入。

  • 目标函数：最大化装入的数量 $$ \max \sum_{i=1}^{n} x_i $$
  • 约束条件： $$ \sum_{i=1}^{n} w_i x_i \le C, \quad x_i \in \{0, 1\} $$

贪心策略 (Greedy Strategy)

对于这个问题，直觉往往就是正确的。

1. 核心策略：重量最轻者优先 (Lightest First)

为了装入更多数量的集装箱，我们应该尽可能留出空间。每一个被选中的集装箱都应该尽可能少地消耗船的载重。因此，贪心策略就是： 优先选择重量最小的物品 。

2. 算法步骤

  1. 排序 ：将所有集装箱的重量 wi 按从小到大（非递减）的顺序排序。
  2. 循环选择 ：
  • 从最轻的集装箱开始，依次尝试装入。
  • 如果当前集装箱的重量 ≤ 船的剩余载重，就装入，并减少剩余载重。
  • 如果当前集装箱装不下，由于后面的更重，肯定也装不下，算法直接结束。

证明贪心选择策略

这一步的核心是证明：在所有最优方案中，一定存在一个方案包含了重量最轻的 1 号集装箱。

  • 前提条件 ：假设集装箱已按重量从小到大排序 w1 ≤ w2 ≤ … ≤ wn。
  • 假设最优解 ：设 X = {x1, x2, …, xn} 是一个最优解（装入箱子最多的方案），其中 k 是该方案中装入的最轻集装箱的索引，即 k = min {i|xi = 1}。
  • 分类讨论 ：
  1. 情况 1（k = 1） ：如果最优解本来就包含了最轻的 1 号箱，证明结束。
  2. 情况 2（k > 1） ：如果最优解没装 1 号箱，而是装了更重的 k 号箱。
  • 构造新解 ：我们用 1 号箱替换掉 k 号箱，得到新方案 Y。即令 y1 = 1, yk = 0，其余物品选取状态与 X 保持不变。
  • 证明新解的合法性与最优性 ：
  • 重量限制 ：由于 w1 ≤ wk，替换后的总重量 ∑wiyi = w1 − wk + ∑wixi ≤ ∑wixi ≤ C。这意味着新方案 Y 依然没有超过载重。
  • 箱子数量 ：新方案 Y 的箱子总数 ∑yi 等于原最优解 X 的箱子总数 ∑xi。
  • 结论 ：既然 Y 合法且数量也是最多的，说明 优先装入最轻的集装箱可以使总箱数最大化 。

2. 最优子结构性质证明（证明“剩下的”也能这么选）

这一步证明：当你装入最轻的集装箱后，剩下的问题依然可以用同样的贪心策略解决。

  • 原问题与子问题 ：设原问题是在容量为 C 时从 {1, 2, …, n} 中选。当你根据贪心策略选了 1 号箱（x1 = 1）后，问题变成了：在容量为 C − w1 的情况下，从剩余的集装箱 {2, 3, …, n} 中进行选择。
  • 证明逻辑 ：如果 {x1, x2, …, xn} 是原问题的最优解，那么其中的子集 {x2, x3, …, xn} 必然是容量为 C − w1 时子问题的最优解。
  • 直观理解 ：如果子问题有更好的解（能装更多箱子），那么把它和 1 号箱结合，就会得到一个比原最优解还要好的方案，这与前提矛盾。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void Loading(int x[], Type w[], Type c, int n) {
    // 创建一个辅助数组 t，大小为 n+1（适应 1-based indexing）
    int *t = new int[n+1];
  
    // 关键步骤：间接排序
    // 输入：w (重量), n (个数)
    // 输出：t (排序后的索引)
    // 此时，t[1] 是最轻物品的ID，t[n] 是最重物品的ID
    Sort(w, t, n); 

    // 初始化解向量 x，默认全部为 0 (都不装)
    for (int i = 1; i <= n; i ++)
        x[i] = 0;

    // 贪心循环
    // 条件1：i <= n (还没遍历完)
    // 条件2：w[t[i]] <= c (当前第 i 轻的物品重量 <= 剩余容量)
    for (int i = 1; i <= n && w[t[i]] <= c; i ++) {
        // x[t[i]] = 1：标记原始编号为 t[i] 的物品被选中
        x[t[i]] = 1;
  
        // 更新剩余容量：减去当前第 i 轻物品的重量
        c -= w[t[i]];
    }
  
    // 注意：这里缺少了 delete[] t; 存在内存泄漏风险
}

总时间复杂度 T(n) 是各部分之和：

$$ T(n) = \underbrace{O(n \log n)}_{\text{排序}} + \underbrace{O(n)}_{\text{初始化}} + \underbrace{O(n)}_{\text{贪心选择}} $$

最终时间复杂度：

O(nlog n)

哈夫曼编码

贪心选择性质

命题： 设字符集 C 中频率最低的两个字符为 x 和 y，则存在一棵最优前缀码树 T，使得 x 和 y 是深度最深的兄弟叶节点。

证明过程（交换论证法）：

  1. 初始假设 ：设 T 是一棵最优前缀码树。在 T 中，设 b 和 c 是深度最深（码长最长）的一对兄弟叶节点。不妨设 f(b) ≤ f(c) 且已知在T中有两个非最深的频率最高的节点，x，y，不妨设 f(x) ≤ f(y)。

  2. 构造新树 T′**** ：由于 x, y 是全局频率最小的，必有 f(x) ≤ f(b) 且 f(y) ≤ f(c)。我们将 x 与 b 交换， y 与 c 交换，得到新树 T′。

  3. 计算代价差： 对比 T 与 T′ 的总权路径长度（代价）：

    B(T) − B(T′) = ∑c ∈ Cf(c)dT(c) − ∑c ∈ Cf(c)dT′(c)

B(T) − B(T′) = [f(x)dT(x) + f(b)dT(b) + f(y)dT(y) + f(c)dT(c)] − [f(x)dT′(x) + f(b)dT′(b) + f(y)dT′(y) + f(c)dT′(c)]

B(T) − B(T′) = f(x)dT(x) + f(b)dT(b) + f(y)dT(y) + f(c)dT(c) − [f(x)dT(b) + f(b)dT(x) + f(y)dT(c) + f(c)dT(y)]

经过代数化简（仅 x, y, b, c 的项未抵消）：

B(T) − B(T′) = (f(b) − f(x))(dT(b) − dT(x)) + (f(c) − f(y))(dT(c) − dT(y))

4.结论 ：

  • 因为 f(b) ≥ f(x) 且 f(c) ≥ f(y)（频率最小性）
  • 因为 dT(b) ≥ dT(x) 且 dT(c) ≥ dT(y)（b, c 在最深层）
  • 所得结果  ≥ 0，即 B(T′) ≤ B(T)。
  • 由于 T 已经是最优的， T′ 的代价只能等于 T。故 T′ 的码长仍然是最短的，即 T′ 是最优前缀码，并且其最小频率的x、y具有最深的深度（最长的编码），且只有最后一位不同

这证明了：贪心选择（合并最小的两个）不会错过全局最优解。

最优子结构性质

命题： 将 x 和 y 合并为新字符 z（频率 f(z) = f(x) + f(y)），得到子问题 C′。若 T′ 是 C′ 的最优树，则将 z 替换回 x, y 得到的树 T 必是原问题 C 的最优树。

关键点 1：建立原问题与子问题的代价关系

  • 递推表达式：原树 T 的平均码长 B(T) 可以用子树 T′ 的码长 B(T′) 表示为： B(T) = B(T′) + f(x) + f(y)
  • 深度关系推导 ：因为 x, y 是 z 的子节点，所以深度满足 dT(x) = dT(y) = dT′(z) + 1。
  • 代数关系： f(x)dT(x) + f(y)dT(y) = (f(x) + f(y))(dT′(z) + 1)  = f(x) + f(y) + (f(x) + f(y))dT′(z)  = f(x) + f(y) + f(z)dT′(z)

关键点 2：采用反证法证明 T′ 是最优的

  1. 假设 ：存在另一个树 T″ 是子问题 C′ 的更优前缀码，即满足 B(T′) > B(T″)。

  2. 构造 ：在树 T″ 中，将节点 z（作为叶子节点）替换为其子节点 x, y，从而得到原问题 C 的一个解 T‴。

  3. 计算 T‴ 的代价：根据上述关键点 1 的关系，可得：

    B(T‴) = B(T″) + f(x) + f(y)

  4. 得出矛盾： 由于假设 B(T″) < B(T′)，则：

    B(T‴) = B(T″) + f(x) + f(y) < B(T′) + f(x) + f(y) = B(T)

    这意味着 T‴ 是比最优树 T 更优的解，这与“T 是原问题的最优解”这一前提矛盾。

结论 ：因此 T′ 必然是子问题的最优解，最优子结构性质得证。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


// 哈夫曼树节点结构
struct Node {
    char ch;        // 字符（内部节点可为空）
    int freq;       // 频率
    Node *left, *right;

    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 比较仿函数：构造最小堆 (Min-Heap)
struct Compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq; // 频率小的优先级高
    }
};

// 递归遍历树，生成编码表
void generateCodes(Node* root, string str, map<char, string>& huffmanCode) {
    if (!root) return;

    // 叶子节点：存储编码
    if (!root->left && !root->right) {
        huffmanCode[root->ch] = str;
    }

    generateCodes(root->left, str + "0", huffmanCode);
    generateCodes(root->right, str + "1", huffmanCode);
}

// 构建哈夫曼树并返回根节点
Node* buildHuffmanTree(const map<char, int>& freqs) {
    priority_queue<Node*, vector<Node*>, Compare> pq;

    // 1. 将所有字符作为叶子节点放入优先队列
    for (auto const& [ch, freq] : freqs) {
        pq.push(new Node(ch, freq));
    }

    // 2. 贪心合并：不断取出两个最小频率节点
    while (pq.size() != 1) {
        Node *left = pq.top(); pq.pop();
        Node *right = pq.top(); pq.pop();

        // 创建新内部节点 z，频率为子节点之和 f(z) = f(x) + f(y)
        int sum = left->freq + right->freq;
        Node *node = new Node('\0', sum);
        node->left = left;
        node->right = right;
        pq.push(node);
    }

    return pq.top(); // 最终剩下的即为根节点
}

时间复杂度分析

  • 构建堆 ：O(n)，其中 n 是字符集大小。
  • 合并过程 ：共进行 n − 1 次合并，每次弹出和压入堆的操作为 O(log n)，总计 O(nlog n)。
  • 总复杂度 ：O(nlog n)。

最小生成树

MST 性质 (Cut Property)

设 G = (V, E) 是一个连通带权无向图，边 (u, v) 的权值为 w(u, v)。

性质描述： 设 U 是顶点集 V 的一个真子集（即 U ⊂ V 且 U ≠ ∅）。如果 (u, v) 是连接 U 和 V − U 的所有边（称为横切边）中权值最小的一条边，那么一定存在一棵最小生成树 (MST) 包含边 (u, v)。

证明 (反证法)

  1. 假设： 假设图 G 的任何一棵最小生成树都不包含这条权值最小的横切边 (u, v)。

  2. 构造矛盾：

    • 设 T 是 G 的一棵最小生成树。根据假设，(u, v) ∉ T。

    • 由于 T 是生成树，它包含连接所有顶点的路径。因此，在 T 中必然存在一条从 u 到 v 的唯一路径。

    • 因为 u ∈ U 且 v ∈ V − U，这条路径必然要从集合 U 跨越到集合 V − U。这意味着路径上至少有一条边 (x, y) 也是横切边（即 x ∈ U, y ∈ V − U）。

    • 根据 MST 性质的前提条件，(u, v) 是所有横切边中权值最小的，所以有 w(u, v) ≤ w(x, y)。

    • 现在，我们构造一个新的图 T′：将边 (u, v) 加入 T，并删除边 (x, y)。

      T′ = (T − {(x, y)}) ∪ {(u, v)}

    • 连通性分析：加入 (u, v) 会在 T 中形成一个环，而删除环上的另一条边 (x, y) 会打破这个环，同时保持图的连通性（因为 (x, y) 和 (u, v) 都在跨越切口的路径上）。因此 T′ 仍然是一棵生成树。

    • 权值分析：

      w(T′) = w(T) − w(x, y) + w(u, v)

      由于 w(u, v) ≤ w(x, y)，则 w(T′) ≤ w(T)。

  3. 结论：

    • 如果 w(u, v) < w(x, y)，则 w(T′) < w(T)，这与 T 是最小生成树矛盾。
    • 如果 w(u, v) = w(x, y)，则 w(T′) = w(T)，说明 T′ 也是一棵最小生成树，且它包含了 (u, v)。这与“任何 MST 都不包含 (u, v)”的假设矛盾。

综上所述，假设不成立，边 (u, v) 一定属于某棵最小生成树。

Prim 算法

Prim 算法是 MST 性质的直接应用。

算法思路：

  1. 维护一个集合 S，初始时只包含任意一个起始顶点（例如 S = {1}）。
  2. 在所有连接 S 和 V − S 的边中，选择权值最小的那条边 (u, v) （其中 u ∈ S, v ∈ V − S）。
  3. 将顶点 v 加入集合 S，并将边 (u, v) 加入最小生成树。
  4. 重复步骤 2 和 3，直到 S 包含所有顶点。

时间复杂度：

  • 使用邻接矩阵 + 数组实现：O(V2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
 * 图的结构体定义
 */
typedef struct {
    char vexs[MAX];       // 顶点集合 (例如: 'A', 'B'...)
    int matrix[MAX][MAX]; // 邻接矩阵 (存储边权值)
    int vexnum;           // 顶点数量
    int edgenum;          // 边数量
} Graph;


/**
 * Prim 最小生成树算法
 * 核心思想：贪心算法。每次从“未被选入生成树的顶点”中，找一个距离“生成树集合”最近的顶点加入。
 *
 * @param G      图结构体 (包含 vexs 顶点数组, matrix 邻接矩阵, vexnum 顶点数)
 * @param start  从第 start 个顶点开始生成 (索引)
 */
void prim(Graph G, int start) {
  
    // weights[] 是核心辅助数组。
    // 含义：weights[i] 保存了顶点 i 到“当前最小生成树集合”的最小权值（距离）。
    // 特殊约定：如果 weights[i] == 0，表示顶点 i 已经被加入到了最小生成树中（已访问）。
    int weights[G.vexnum]; 
  
    int index = 0;              // 结果数组 prim 的索引计数器
    char prim[G.vexnum];        // 用于保存最小生成树的顶点顺序（结果）
    int total = 0;              // 记录最小生成树的总权值
  
    // --- 步骤 1：初始化 ---
  
    //先把起始顶点 start 加入集合，所以距离置为 0
    weights[start] = 0; 
  
    // 初始化 weights 数组
    // 将 start 顶点到其他所有顶点的距离存入 weights
    for(int i = 0; i < G.vexnum; i++) {
        weights[i] = G.matrix[start][i];
    }
  
    // 将起始顶点放入结果数组
    prim[index++] = G.vexs[start];
  
    // --- 步骤 2：循环寻找剩余的 n-1 个顶点 ---
  
    for(int i = 0; i < G.vexnum; i++) {
        // 由于 start 已经加入，跳过一次循环计数（这里只是为了控制循环次数为 n-1 次）
        if(i == start) continue;
  
        int k = -1;      // 用于记录当前找到的距离最近的顶点下标
        int min = INF;   // min 用来存放当前的最小权值，初始化为无穷大
  
        // 2.1 寻找最近顶点：
        // 遍历所有顶点，找出未加入生成树（weights!=0）且距离生成树最近（weights最小）的顶点
        for(int j = 0; j < G.vexnum; j++) {
            // weights[j] != 0 代表该点还没被选中
            // weights[j] < min 代表发现了更近的点
            if(weights[j] != 0 && weights[j] < min) {
                min = weights[j];
                k = j; // 记录下这个顶点的下标
            }
        }
  
        // 如果 k 还是 -1，说明剩下的顶点都无法到达（图不连通），跳出循环
        if(k == -1) break;
  
        // 2.2 将找到的顶点 k 加入生成树：
        weights[k] = 0;             // 标记为 0，表示已加入生成树，以后不再重复选取
        prim[index++] = G.vexs[k];  // 存入结果数组
        total += min;               // 累加权值
  
        // 2.3 更新距离（松弛操作）：
        // 新加入顶点 k 后，可能通过 k 到达其他顶点的距离比原来更近了
        // 所以要遍历 k 的所有邻接点，更新 weights 数组
        for(int j = 0; j < G.vexnum; j++) {
            // 如果顶点 j 还没加入生成树 (weights[j] != 0)
            // 且从 k 到 j 的距离 (G.matrix[k][j]) 小于目前记录的距离 weights[j]
            if(weights[j] != 0 && weights[j] > G.matrix[k][j]) {
                weights[j] = G.matrix[k][j]; // 更新更短的距离
            }
        }
    }
}

// --- 第三步：打印结果 ---
    printf("PRIM最小生成树结果 (起始点 %c):\n", G.vexs[start]);
  
    // 打印节点顺序
    printf("节点生成顺序: ");
    for (int i = 0; i < index; i++) {
        printf("%c ", prim[i]);
    }
    printf("\n");

    // 打印总权值
    printf("最小生成树总权值: %d\n", total);

}

Kruskal 算法

Kruskal 算法也是基于 MST 性质，但它是从边的角度出发。

算法思路：

  1. 将图中所有边按权值从小到大排序。
  2. 初始时，每个顶点自成一个连通分量。
  3. 依次考察排序后的每条边 (u, v)：
    • 如果 u 和 v 属于不同的连通分量，则选择这条边，并合并这两个分量（因为这条边是连接这两个分量的最短边，符合 MST 性质）。
    • 如果 u 和 v 已经属于同一个连通分量，则舍弃这条边（否则会形成环）。
  4. 重复步骤 3，直到选择了 n − 1 条边。

实现细节： 通常使用 并查集 (Union-Find) 数据结构来快速判断两个顶点是否属于同一个连通分量以及合并分量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <stdio.h>
#include <stdlib.h>

#define MAX 100         // 最大顶点数
#define INF 65535       // 无穷大

/**
 * 边结构体：用于 Kruskal 算法中的边排序
 */
typedef struct {
    char start;   // 起点 (例如 'A')
    char end;     // 终点 (例如 'B')
    int weight;   // 权值
} Edge;

/**
 * 图结构体
 */
typedef struct {
    char vexs[MAX];       // 顶点集合
    int matrix[MAX][MAX]; // 邻接矩阵
    int vexnum;           // 顶点数
    int edgenum;          // 边数
} Graph;

/**
 * 辅助函数：根据顶点字符获取索引
 */
int get_position(Graph G, char ch) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vexs[i] == ch)
            return i;
    }
    return -1;
}

/**
 * 辅助函数：从邻接矩阵中提取所有的边
 * 返回值：指向 Edge 数组的指针
 */
Edge* get_edges(Graph G) {
    int index = 0;
    Edge* edges = (Edge*)malloc(G.edgenum * sizeof(Edge));
  
    for (int i = 0; i < G.vexnum; i++) {
        // j 从 i+1 开始，只遍历矩阵的上三角，避免重复和自身循环
        for (int j = i + 1; j < G.vexnum; j++) {
            if (G.matrix[i][j] != INF) {
                edges[index].start = G.vexs[i];
                edges[index].end = G.vexs[j];
                edges[index].weight = G.matrix[i][j];
                index++;
            }
        }
    }
    return edges;
}

/**
 * 辅助函数：对边数组进行排序 (冒泡排序，从小到大)
 * 贪心策略的核心：优先选择短边
 */
void sort_edges(Edge* edges, int edgenum) {
    for (int i = 0; i < edgenum - 1; i++) {
        for (int j = 0; j < edgenum - 1 - i; j++) {
            if (edges[j].weight > edges[j + 1].weight) {
                Edge temp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = temp;
            }
        }
    }
}

/**
 * 核心辅助函数：查找顶点的“终点”（所在集合的代表/根节点）
 * 用于判断两个点是否已经在同一个连通分量中
 */
int get_end(int vends[], int i) {
    // 只要当前点指向的不是自己，就说明它还有上级，继续往上找
    while (vends[i] != i) {
        i = vends[i];
    }
    return i;
}

/**
 * Kruskal 最小生成树算法
 */
void kruskal(Graph G) {
    int i, m, n;
    int index = 0;          // 结果数组索引
    int length = 0;         // 最小生成树总权值
    int vends[MAX];         // 并查集数组：记录每个点的父节点
    Edge rets[MAX];         // 结果数组：保存最终选用的边
    Edge* edges;            // 所有的边

    // 1. 获取图中所有的边
    edges = get_edges(G);

    // 2. 将边按照权值从小到大排序
    sort_edges(edges, G.edgenum);

    // 3. 初始化并查集
    // 初始状态：每个顶点的终点都是它自己（互不连通）
    for (i = 0; i < G.vexnum; i++) {
        vends[i] = i; 
    }

    // 4. 遍历每一条边（从小到大）
    for (i = 0; i < G.edgenum; i++) {
        // 获取这条边起止点的索引
        int p1 = get_position(G, edges[i].start);
        int p2 = get_position(G, edges[i].end);

        // 查找 p1 和 p2 所在的集合代表（终点）
        m = get_end(vends, p1);
        n = get_end(vends, p2);

        // 5. 判断是否形成环路
        // 如果 m != n，说明两个点目前在不同的集合中，可以连接
        if (m != n) {
            vends[m] = n;           // 【合并集合】将 m 的终点指向 n
            rets[index++] = edges[i]; // 将这条边加入结果
            length += edges[i].weight;
        }
        // 如果 m == n，说明这两个点已经连通了，再加边就是环，所以跳过（贪心丢弃）
    }

    // 6. 打印结果
    printf("Kruskal 最小生成树结果 (总权值=%d):\n", length);
    for (i = 0; i < index; i++) {
        printf("(%c, %c) 权值:%d\n", rets[i].start, rets[i].end, rets[i].weight);
    }

    // 释放动态分配的内存
    free(edges);
}

int main() {
    // 构建示例图：A, B, C, D, E
    char vexs[] = {'A', 'B', 'C', 'D', 'E'};
    int matrix[5][5] = {
        /* A */ {0,   2,   4,   7,   INF},
        /* B */ {2,   0,   1,   INF, 5},
        /* C */ {4,   1,   0,   INF, 6},
        /* D */ {7,   INF, INF, 0,   3},
        /* E */ {INF, 5,   6,   3,   0}
    };

    Graph G;
    G.vexnum = 5;
    G.edgenum = 7; // 图中有 7 条有效边

    for (int i = 0; i < G.vexnum; i++) {
        G.vexs[i] = vexs[i];
        for (int j = 0; j < G.vexnum; j++) {
            G.matrix[i][j] = matrix[i][j];
        }
    }

    kruskal(G);

    return 0;
}

时间复杂度：

  • 排序边：O(Elog E)
  • 并查集操作：O(Eα(V)) （α 为阿克曼函数的反函数，极小，可视为常数）
  • 总复杂度：O(Elog E)

回溯

0-1背包问题

解向量： < x1, x2, .....xn> xi 表示第i个物品选或不选

解空间树：

1766566630155 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

// 新增全局变量
int x[N];      // 当前解：x[i]=1 表示第i个物品放入，0表示不放入
int bestx[N];  // 最优解：用来保存最终结果
/**Type cw = 0;        // 当前重量
Type cv = 0;        // 当前价值
Type bestp = 0;     // 当前最优价值
c 背包容量
 * 计算上界函数 (Bound)
 * 作用：预测当前分支理论上能达到的最高价值
 */
Type Bound(int i) {
    Type cleft = c - cw; // 剩余容量
    Type b = cv;         // 当前已获价值
  
    // 尽力装入完整物品
    while (i <= n && w[i] <= cleft) {
        cleft -= w[i];
        b += v[i];
        i++;
    }
  
    // 如果还有空间，装入下一个物品的一部分（分数背包逻辑）
    if (i <= n) {
        b += v[i] / w[i] * cleft;
    }
    return b;
}

/**
 * 回溯核心函数
 * i: 当前处理第 i 个物品
 */


void BackTrack(int i) {
    // 1. 达到叶子节点
    if (i > n) {
        bestp = cv;
  
        // 【修改点1】：当找到最优解时，把当前的路径 x 复制给 bestx
        for (int j = 1; j <= n; j++) {
            bestx[j] = x[j];
        }
        return;
    }

    // 2. 左子树：放入物品 i
    if (cw + w[i] <= c) { 
        x[i] = 1;      // 【修改点2】：记录当前物品 i 被选中
        cw += w[i];
        cv += v[i];
  
        BackTrack(i + 1);
  
        cw -= w[i];    // 回溯
        cv -= v[i];
        x[i] = 0;      // 【回溯】：虽然这一步不写逻辑上也没错（会被覆盖），但写上更严谨
    }

    // 3. 右子树：不放入物品 i
    if (Bound(i + 1) > bestp) { 
        x[i] = 0;      // 【修改点3】：记录当前物品 i 不被选中
        BackTrack(i + 1);
    }
}

该算法的 最坏时间复杂度 是：

O(n ⋅ 2n)

其中：

  • n 是物品的数量。
  • 2n 来自于解空间树的大小（子集树）。
  • 额外的 n 系数来自于 Bound 函数的计算开销。

详细分析

我们可以从 解空间结构 和 节点计算耗时 两个方面来分析。

  1. 解空间树（Subset Tree）

0-1背包问题的解空间是一棵 子集树 。

  • 对于 n 个物品，每个物品都有 2 种选择（选 或 不选）。
  • 这构成了一棵二叉树，树的深度为 n。
  • 总节点数 ：满二叉树的节点数接近 2n + 1，即 O(2n) 量级。
  1. 单个节点的计算开销

在递归过程的每一个节点（即每次调用 BackTrack），我们可能会调用 Bound(i) 函数来计算上界。

  • Bound 函数内部包含一个 while 循环，最坏情况下会扫描剩余的所有物品。
  • 因此，Bound 函数的时间复杂度是 O(n) 。
  1. 综合复杂度
  • 最坏情况 ：如果你的剪枝策略（Bound 函数）失效（例如数据构造得很特殊，使得每次计算出的上界都比 bestp 大），算法就必须遍历整棵树。
  • 计算公式： 总时间 ≈ 节点总数 × 单节点开销 ≈ 2n × n

N皇后

解向量设计：给棋盘上的行和列从1到N编号，同时也给皇后1-N编号，假设皇后i放在第i行，则问题可以表示为n元组

[x1, x2.....xi, xj....xN]

xi 表示i皇后的列号1766566658610

  1. 列约束：当 i ≠ j 时，要求 xi ≠ xj（即不同行不能在同一列）。
  2. 对角线约束：要求 |i − j| ≠ |xi − xj|（即不能在同一对角线上）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
// ==========================================
// 1. 约束函数 Place (与迭代版完全一样)
// ==========================================
bool Place(int k) {
    for (int i = 1; i < k; i++) {
        // 检查：是否同列 || 是否同对角线
        if ((x[i] == x[k]) || (abs(i - k) == abs(x[i] - x[k]))) {
            return false;
        }
    }
    return true;
}

// ==========================================
// 2. 递归回溯函数 Backtrack
//    t 代表当前正在处理第 t 行
// ==========================================
void Backtrack(int t) {
    // --- 终止条件 (Base Case) ---
    // 如果 t > n，说明前 n 行都已经放好了，找到了一个解
    if (t > n) {
        total_solutions++;
        // 打印这个解（可选）
        cout << "解 " << total_solutions << ": ";
        for (int i = 1; i <= n; i++) cout << x[i] << " ";
        cout << endl;
        return; 
    }

    // --- 递归步骤 (Recursive Step) ---
    // 尝试当前行 t 的每一列 (从 1 到 n)
    for (int j = 1; j <= n; j++) {
        x[t] = j; // 尝试把第 t 行皇后放在第 j 列

        // 如果放在这里不冲突 (满足约束)
        if (Place(t)) {
            Backtrack(t + 1); // 【递归】深入下一层，去放第 t+1 行
        }
  
        // 【回溯】(Backtracking)
        // 注意：递归函数执行完返回这里时，意味着 t+1 层及其子树都搜完了。
        // 我们不需要显式写 x[t]=0，因为下一次循环 j++ 会直接覆盖 x[t] 的值。
        // 这就是递归的“自动回溯”特性。
    }
}
  1. 理论上限（最坏情况）

如果我们使用回溯法（Backtracking）来寻找所有解，算法的核心逻辑是逐行放置皇后。

  • 第 1 行 ：有 N 种选择（即放在第 1 列到第 N 列）。
  • 第 2 行 ：为了避免列冲突，剩下 N − 1 种选择。
  • 第 3 行 ：剩下 N − 2 种选择。
  • …
  • 第 N 行 ：只剩下 1 种选择。

如果不考虑对角线的限制，仅考虑列不冲突，可能的状态总数就是 N × (N − 1) × (N − 2) × … × 1 = N!。

因此，算法搜索空间的上界是 O(N!) 。

  1. 实际运行效率（剪枝的影响）

虽然理论上界是 O(N!)，但在实际运行中，我们加入了 对角线冲突检测 （即你的代码中的 is_ok 函数或布尔数组判断）。

  • 一旦发现当前位置与之前的皇后在对角线上冲突，算法会立即停止该分支的搜索（剪枝/Pruning）。
  • 这意味着算法根本不会遍历完整的 N! 个节点。实际访问的节点数远小于 N!。
  • 尽管如此，对于非常大的 N，其增长速度仍然是指数级甚至是超指数级的。
  1. 具体代码实现的细节影响

你之前提供的代码中，is_ok 函数的实现方式也会微调复杂度：

1
2
3
4
5
6
7
// 你的 is_ok 函数
bool is_ok(int row) {
    for (int i = 0; i < row; i++) { // 这里有一个 O(N) 的循环
        if (...) return false;
    }
    return true;
}
  • 常规回溯 ：如果使用布尔数组（colUsed, diag1, diag2）来判断冲突，判断操作是 O(1) 的。此时总复杂度接近 O(N!)。
  • 你的回溯 ：由于 is_ok 内部有一个循环，判断一个位置是否合法的代价是 O(N)。因此，严格来说，你的代码的时间复杂度上界是 O(N ⋅ N!) 。

m图着色

代码实现

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void Color::Backtrack(int t)
{
 if (t>n) {
 sum++;
 for (int i=1; i<=n; i++)
 cout << x[i] << ' ';
 cout << endl;
 }
 else{
 for (int i=1;i<=m;i++) {
 x[t]=i;
 if (Ok(t)) Backtrack(t+1);
 }}
}
bool Color::Ok(int k)
{// 检查颜色可用性
 for (int j=1;j<k;j++)
 if ((a[k][j]==1)&&(x[j]==x[k])) return false;
 return true;
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * 非递归 m 图着色算法
 * n: 顶点数, m: 颜色数, a: 邻接矩阵, x: 解向量
 */
void m_coloring(int n, int m, bool a[][MAXN], int x[]) {
    // 1. 初始化解向量
    for (int i = 1; i <= n; i++) {
        x[i] = 0; // x[i]=0 表示该顶点尚未着色
    }

    int k = 1; // 从第一个顶点开始处理

    // 外层循环：控制顶点 1, 2, ..., n 的着色过程
    while (k >= 1) { 
        x[k] = x[k] + 1; // 为当前顶点 k 尝试下一种颜色

        // 内层循环：寻找顶点 k 的下一个可用颜色
        while (x[k] <= m && !OK(k, a, x)) { 
            x[k] = x[k] + 1; // 如果当前颜色冲突，尝试颜色编号 +1
        }

        // 判断是否为顶点 k 找到了合适的着色
        if (x[k] <= m) { 
            // 成功找到颜色
            if (k == n) {
                // 如果当前是最后一个顶点，说明找到一个可行解
                // 输出解向量或进行处理
                break; 
            } else {
                // 如果不是最后一个顶点，继续处理下一个顶点 k+1
                k = k + 1; 
            }
        } else { 
            // 没有为顶点 k 找到合适着色（x[k] > m），触发回溯
            x[k] = 0; // 撤销当前顶点的着色状态
            k = k - 1; // 回退到前一个顶点，尝试它的其他分支
        }
    }
}

对于解空间树中的每一个 非叶节点 ，在扩展它的子节点时，最坏情况下的耗时是 O(mn) 。

1766566684681
  • m 的含义 ：当前节点有 m 个分叉（对应 m 种颜色），算法需要尝试每一个子节点。
  • n 的含义 ：对于这 m 个可能的颜色，每一个都要调用一次 OK 函数。OK 函数需要检查当前顶点与图中其它最多 n − 1** 个顶点的相邻关系及颜色冲突，耗时为 O(n)**。
  • 结论 ：因此，处理一个父节点以产生其所有子节点所需的总时间是 m × O(n) = O(mn)。

$$ \sum_{i=0}^{n} m^i(mn) $$

  • ∑mi ：这是解空间树中各层节点的总和。
  • (mn) ：这是在每一层处理节点扩展时的单位工作量。

根据等比数列求和公式推导：

nm(mn − 1)/(m − 1) = O(nmn)

旅行商问题TSP

目标是寻找一条回路，使得总费用（距离）最小化

$$ \min \left\{ \sum_{i=1}^{n-1} w(v_i, v_{i+1}) + w(v_n, v_1) \right\} $$

  • 第一部分 $\sum_{i=1}^{n-1} w(v_i, v_{i+1})$：表示从起点 v1 出发，依次经过其它 n − 1 个城市，直到到达最后一个城市 vn 的路径总长。
  • 第二部分 w(vn, v1)：表示从最后一个城市 vn 回到起点 v1 的距离（闭合回路）。
  • w(vi, vj) 或 w(i, j)**** ：表示城市 i 和城市 j 之间的直接距离（权重）。
  • w(vi, vj) = ∞ ：表示两个城市之间没有直接路径（非完全图的情况）。
  • 顶点的编号 ：将 n 个城市简单编号为 1, 2, …, n。
  • 解空间大小 = (n − 1)!****
  • 推导逻辑 ：虽然总共有 n 个城市，全排列是 n!，但由于TSP是回路问题，起点的选择不影响路径的总长度（是一个圈）。为了消除重复计算，我们固定起点（如节点1），剩下的 n − 1 个节点进行全排列。

剪枝

剪枝/约束条件 1：连通性剪枝 (Feasibility)

如果当前正在考虑的顶点 j，与当前已经走过的部分路径中的末端结点 i 没有边相连（即 w[i, j] = ∞），则放弃搜索 j 所在分支。

剪枝/约束条件 2：最优性剪枝 (Optimality)

令到第 i 层结点为止，构造的部分解路径为  < x1, x2, …, xi>

该路径的当前权值总和 cw (Current Weight) 为：

$$ cw = \sum_{j=1}^{i-1} w(x_j, x_{j+1}) $$

剪枝逻辑：

如果 当前部分路径的开销 cw 已经大于或等于 当前已找到的最优解（Best Weight, bestw），则剪枝。

  • 为什么剪枝？ 即使剩下的路径长度为0（不可能），这条路的总长度也已经超过了之前找到的一条完整回路（最优解）。继续往下搜只会得到更差的结果，纯属浪费时间。

解空间树

1766565547188

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 假设最大城市数量 N
#define N 100 
#define INF 99999999 // 表示无穷大，即无通路

int n;               // 城市数量
int w[N][N];         // 邻接矩阵，w[i][j] 表示城市 i 到 j 的距离
int x[N];            // 当前搜索过程中的部分路径 (解向量)
int bestx[N];        // 记录当前找到的最优路径
int cw = 0;          // (Current Weight) 当前已经走过的路径总长度
int bestw = INF;     // (Best Weight) 当前找到的最优回路的长度



void BacktrackTSP(int i) {
    // ==========================================================
    // 1. 叶子节点处理：到达递归底层 (i == n)
    // ==========================================================
    if (i == n) {
        // 检查两个条件：
        // 1. 倒数第二个城市 x[n-1] 到 最后一个城市 x[n] 是否有路
        // 2. 最后一个城市 x[n] 到 起点 1 是否有路 (构成回路)
        if (w[x[n-1]][x[n]] != INF && w[x[n]][1] != INF) {
  
            // 判断当前完整回路的费用是否比已知的最优解更小
            if (cw + w[x[n-1]][x[n]] + w[x[n]][1] < bestw) {
  
                // 更新最优权值
                bestw = cw + w[x[n-1]][x[n]] + w[x[n]][1];
  
                // 记录当前最优路径
                for (int j = 1; j <= n; j++) {
                    bestx[j] = x[j];
                }
            }
        }
        return;
    }

    // ==========================================================
    // 2. 递归扩展子树：遍历当前层所有可能的选择
    // ==========================================================
    else {
        // 尝试每一个还未访问的城市（通过交换位置实现排列生成）
        for (int j = i; j <= n; j++) {
  
            // --- 剪枝 / 约束条件检查 ---
            // 1. 连通性剪枝：x[i-1] 到 待选城市 x[j] 必须有路
            // 2. 最优性剪枝：当前花费 + 新的一步花费 必须 < 当前最优解 bestw
            if (w[x[i-1]][x[j]] != INF && (cw + w[x[i-1]][x[j]] < bestw)) {
  
                // [前进]：准备搜索下一层
                swap(x[i], x[j]);           // 1. 交换：将选中的城市 x[j] 放到当前位置 i
                cw += w[x[i-1]][x[i]];      // 2. 累加：更新当前路径长度
  
                // [递归]：深度优先搜索下一层
                BacktrackTSP(i + 1);        //
  
                // [回溯]：恢复状态，准备尝试 loop 中的下一个 j
                cw -= w[x[i-1]][x[i]];      // 1. 减去刚才加上的距离
                swap(x[i], x[j]);           // 2. 交换回来：恢复数组顺序
            }
        }
    }
}

时间复杂度

O(n!)

(注：更精确的说法是 O((n − 1)!)，但在大O表示法中，通常简写为阶乘级 O(n!))