xjtuse算法设计与分析

第一章 算法概述

1.1 主定理和递归树

1.2 复杂度分析

​ 在算法中，时间复杂度是个时间增长率概念，而不是时间概念

举个例子：

假设我们有两个算法，分别是 O(n) 和 O(n²)：

• 如果输入规模 n=1000，则 O(n) 可能需要 1000 次操作，而 O(n²) 可能需要 1000,000 次操作。
• 如果输入规模 n=10,000，O(n) 可能需要 10,000 次操作，而 O(n²) 可能需要 100,000,000 次操作。

也就是说O(1)就是执行一次操作

1.3 NP完全性理论

第2章 递归与分治

2.1 分治思想

理解 使用条件：能分成独立的子问题（>=1），一般采取等分策略或者递减。例如汉诺塔、上台阶等等

2.3 快速幂算法

快速幂算法确实比普通的计算幂方法高效得多。以下是具体原因：

1. 时间复杂度

• 普通方法：计算 a^n 需要进行n−1 次乘法，时间复杂度为 O(n)。
• 快速幂算法：通过分治法将问题规模减半，时间复杂度为 O(log⁡n)。

2. 乘法次数

• 普通方法：需要 n−1 次乘法。
• 快速幂算法：最多需要 2log⁡2n 次乘法。

3. 示例

计算 2^10：

• 普通方法：进行 9 次乘法。
• 快速幂算法：只需 4 次乘法。

long long fastPow(long long a, long long n) {
    long long result = 1; 
    while (n > 0) {
        // 如果当前指数是奇数，将结果乘以当前的底数
        if (n % 2 == 1)  result *= a;
        a *= a;
        n /= 2;
    }
    return result;
}    //递推实现

2.5 Strassen矩阵乘法

Strassen矩阵乘法（Strassen’s Matrix Multiplication）是一种提高矩阵乘法效率的算法，由计算机科学家沃尔夫冈·斯特拉森（Volker Strassen）在1969年提出。该算法通过分治法的思想，减少了传统矩阵乘法的计算复杂度。

Strassen算法的核心思想

Strassen算法的核心思想是分治法：将矩阵分解为较小的子矩阵，并通过递归计算来减少乘法的次数。通过巧妙的分解和合并，Strassen算法能够在减少乘法次数的同时计算矩阵乘积。

Strassen算法的时间复杂度

Strassen算法将标准矩阵乘法中的8个乘法减少到7个乘法，每个乘法操作的规模是 n/2×n/2n/2 n/2n/2×n/2 的子矩阵，这样就将问题规模从 nnn 降到了 n/2n/2n/2。因此，Strassen算法的递归关系为：

T(n)=7T(n/2)+O(n2)T(n) = 7T(n/2) + O(n^2)T(n)=7T(n/2)+O(n2)

通过主定理求解这个递归关系，得到Strassen算法的时间复杂度为：

T(n)=O(nlog⁡27)≈O(n2.81)T(n) = O(n^{_2 7}) O(n^{2.81})T(n)=O(nlog27)≈O(n2.81)

相比传统的 O(n3)O(n^3)O(n3)，Strassen算法通过减少乘法次数，显著提高了矩阵乘法的效率。

2.6 ==棋盘覆盖问题==

看原视频，三张ppt——还有个补充内容没看

L型骨牌覆盖 ### Keys

看起来这个代码并没有解决用 “L” 骨牌来覆盖，而是用单个方块，但实际上因为本题采用的是分治策略，每次都会把大问题划分成四个等性质的小问题，于是给“三个小问题添加的过程”即是放L骨牌的过程！

最后依靠边界处理解决（1*1规模）

2.7 归并排序

void MergeSort(Type a[], int left, int right){
	if(left < right){
		int mid = (left + right) / 2;
		
		MergeSort(a, int left, int mid);
        MergeSort(a, int mid + 1, int right);
        merge(a, b, left, mid, right);          //合并回数组b
        copy(a, b, left, right);				//复制回数组a
	}
}

核心在于先分成多个小问题排序，让后merge

T（n）=O（nlogn），渐进意义下的最优算法(最坏平均都是)，有稳定性

此外还有一种非递归实现：

每次都用数组的相邻的两个块……

2.8 快速排序（改进没看）

template<class Type>
void QuickSort (Type a[], int p, int r){
	if(p < r){
		int q = partition(a, p, r);
		QuickSort(a, p, q - 1);    //是q-1
		QuickSort(a, q + 1, r);
	}
}


partition 的实现具体看视频，很妙

快排在最坏情况会变成O（n2），有 T（n）= T（n - 1）+ n

需要采用随机策略选取分割点来避免这种情况，将随机出的数和第一个数做交换

==快排越有序，情况越坏==

2.9 线性时间选择

给一个无序数组，要求在线性时间内找出第k小的数

不多说，用 RandomizedSelect 算法分治解决，细看视频，有些不好想

2.10 循环赛日程表

把一个2^n 表格分成四份，两份递归，两份复制 …… 代码见视频

非递归实现：一列变两列，两变四，四变八。。

有小结

第3章 动态规划

3.1 动态规划算法原理

分治与动态规划区别：前者分出的子问题是相互独立的，后者则有大量的重复

基本步骤：v

3.2 矩阵连乘问题

给定 N 个矩阵，给定一种计算次序，使它的总数乘次数最小

由结合律知，当做到了“完全加括号”，则连乘积的总数乘数已确定

穷举法基本不行，指数级别复杂度

Items:

• ==两矩阵 a * b, b * c 相乘，数乘数为：s = a * b * c==
• 用一维数组p[n]存储矩阵的行和列数，则第i个矩阵的行和列数分别为 p_i − 1 和 p_i (因为相邻矩阵的前列数等于后行数)

3.3 动态规划问题的基本要素

1. 满足最优子结构性质
2. 存在大量的子重叠问题

eg：此时想，对于斐波那契数列，采用分治还是动态规划？

• 记忆化搜索
• 无后向性

3.4 数字塔问题

1. 找出最优解性质，并刻画其结构特征
2. 最优解的递归定义（写出状态转移方程）
3. 自顶而上的方式计算最优质 （从塔的底部逆向而上，最优解就是顶部的值）
4. 构造最优解 （通过 Traceback 比较是 i+1 层的哪一个来的，得出路径）

3.5 最长公共子序列

挺妙，讲的也很好，看看

真的讲清了值钱树上看不懂的3种转移策略

3.6 凸多边形的最优三角部分

类似于矩阵连乘的语法树，关键点还是写出 ==“状态转移方程”==

建议脱离视频自己看 状态转移方程

3.7 01背包问题

复习

3.8 四柱汉诺塔问题

问题是三柱的扩展，教会了我：

• dp 第一步，给“分析最优子结构” 提供了范式
• dp 对于普通人来说，是真的可以靠 “一步一步的规范” 来提供解决思路的

看视频代码简单

3.9 游艇租赁问题

明白了：3.6以后都是 以 min（， + ）-k 的形式来实现状态转移方程的。相反，之前诸如01背包问题，转移方程中没有 “min（k）”k的变化循环 ！（两种分类）

• 单变量下表递归的复杂度，通常小于双下表

实现也挺妙

==注重dp的步骤范式四步==

第4章 贪心

4.1 活动安排问题

选取 “结束时间最早” 策略

4.2 贪心算法基本要素

贪心算法总是选择当前最优（局部最优），不从整体考虑。又称为“贪心选择算法”

对某些问题可以快速获得整体最优解，对有些只能是近似最优解

贪心:

1. 最优子结构性质

2. 贪心选择性质：子问题协同整体问题最优解

4.3 最优装载

4.4 哈夫曼编码

解决问题：一个编码不能是另一个编码的前缀

前缀码：给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码

定长编码二叉树 和 哈夫曼编码二叉树，==看图==就很好理解

贪心策略：

每次选取选取发生频率最小的两个，把他们结合放回优先队列。。。。。。

4.5 单源最短路径

其实是 Dijkstar （/ˈdaɪkstrə/）算法，看视频的流程图 ==这是贪心原理！！==

复杂度 O（n²）

4.6 最小生成树

• Prim 算法：从1个点开始扩散
• Kruskal 算法：每次选取权值最小的边
• 当边数较多时，Prim 算法占优；当边数较少时， Kruskal算法占优

4.7 多机调度问题

实为NP问题，目前没有最优解

用贪心求的近似解，看图，很清晰

第5章 回溯法

5.1 回溯算法框架

名词

显约束 隐约束 解空间 解空间树

扩展结点 活结点 死节点

遍历：子集树2ⁿ 排列树 n! （排列数最后一层只有一个分支）

5.2 装载问题

问题本身简单，但是 视频的 5：48的那张解空间树的那张图，以及简例说明很好，形象地描述了回溯

• 用==“分解成子问题的表达形式” 代替一步一步仔细想回溯，会更简单== （相当于用了整体隔离法，把内部分给封装了） 具体见11：21

这个video讲的很好，一方面清晰展示了简单例题和模板，另一方面分析了时间复杂度-好

5.3 批作业处理调度

解空间 ：排列数

典

5.5 n皇后问题

讲的很好，说明之前理解不透彻的一个点

将 ”不能同行“ 当作显约束，把“不能同列和斜线” 当作隐约束 ==（其实就是当作剪枝函数！）==

• 但此时生成的是 子集树 ，有256个分支

如果将“不同行与不同列”都当作显约束，那么其实这就会生成 排列数，还有个剪枝函数

• 这个 排列数 效率要比子集树高

Place 和 Backtrack 函数的代码简洁好懂，看 （有错！

xjtuguide

5.6 01背包问题

限界函数 Bound：对右子树进行剪枝 重要，手动减少搜索，比如预估右孩子极其下面能产生的最大价值等

在这个题中，贪心算法求出限界函数值bestp，用来剪枝 这个bestp相当于一个上界，放缩

5.7 最大团问题

子集树，代码比较清晰，可看

学会计算它的复杂性，O(n*2ⁿ)

左子树的剪枝函数是可行性约束函数

5.8 图的m着色问题

子集树 代码清晰，挺妙

是图的问题

5.9 圆排列问题

很好的题目和讲解，以及代码

它还提醒我们：剪枝（约束）函数不一定要是完全的（数学问题中），尤其是当准确的剪枝函数复杂度很高时，可以将得到的最终结果再提出来进行剪枝函数的验证 ！

Tips：

• 去掉镜像排列，可以减少一般的计算量！
• 去重复排列：n个圆中有k个半径相同的圆，则有 k! 个排列，其实只计算一个就够了

改进

• 规定某个排列的首元素一定大于/小于尾元素
• 第i个位置只允许一个半径为k的圆放在这里（标记）

第6章 分支限界法

6.1 分支限界法基本思想

• 以广度优先和最小耗费优先优先的方式搜素问题的子空间树
• 上面两种分别对应队列式（FIFO first in first out）和优先队列式（用优先队列维护生成的子节点）
  
• 好

6.2 装载问题

讲的清楚

FIFO

• 通常叶子节点不入列

改进： 因为是bfs，故用不能用“比较右节点潜力的方式”，而应该采用在左节点入列时就更新bestp

优先队列

• ==当叶子节点成为扩展结点时候才是结束==，并且第一个就是最优解

画维护堆的过程

6.3 布线问题

类似于迷宫找路

6.4 01背包

• 当第一个叶子节点成扩展节点时，==不能保证==就是最优解

6.6 旅行售货员问题

可能类似于单源问题，重点有确定优先级的方法，还是看一看

6.7 小结

• 队列式：需要加入层次标志如-1，或记录下层编号在活结点当中

• 优先队列：大根堆小根堆，插入/删除 o（nlogn）

• 构造解方法（记录选择路径）：记录父节点地址和左孩子标志，回溯法找到最优解。也可。。。

• 子集树的左子树和右子树剪枝策略不同，因为一个是1一个是0

• 但==排列树：n叉树，剪枝策略是相同的==

• 两者结束方式也不同，队列式分支限界法：活结点表为空 （叶子节点不进队列）

• 优先队列：叶子节点成为扩展节点（保证该叶子节点的优先级最大）

第7章 随机化算法

7.1 随机数

线性同余法

7.2 数值随机化算法

1. 随机投点法计算PI值
2. 计算定积分（）
3. 解非线性方程组：看视频，转化为单优化

用随机化算法时间太长，可使用粒子群算法/模拟退火

7.3 Sherwood 算法

利用洗牌算法打破原有规律

• 跳跃表：可在O（logn）时间内支持有序集的搜索
• 完全跳跃表
• 动态维持跳跃表附加指针的平衡性：概率设置k级指针
• 插入操作

7.4 Las Vegas拉斯维加斯算法

• n后
• 整数因子分解（Pollard 算法）

7.5 Monte Carlo算法

一堆概念和定义

k越大（次数越多）正确性越高，近99.99%

• 主元素问题（可用确定性算法去做）
• 素数测试
• Prime 算法是个偏假3/4的蒙特卡洛算法，通过重复调用k次，可以保证错误概率不超过 (1/4)^k

第8章 NP完全性理论

确定性算法（定义）– 随机化算法

• nlogn 被看作多项式时间复杂性，因为logn 是亚线性时间复杂性

• 易解的：

• 难解的：

• P问题
  

• 不可判定性：停机问题

• NP 问题：用不确定性算法在多项式时间内完成的问题 ==P问题属于NP问题==

• NPC问题（NP完全问题） 是NP和NP难问题的交集

• NP难问题

目录总共四种。最后有数学关系总结

题目额外训练

• 矩阵连乘问题

xjtuguide 一份题

5题

• 01背包问题
• 旅行售货员问题
• 两船装载问题
• 批处理作业调度
• n皇后问题 与 四皇后问题
• 最大团问题
• 图的m着色问题
• 圆排列问题
• 连续邮资问题(*)

6题

• 01背包+ 售货员
• 单源最短路径
• 装在问题及改进
• 作业分配问题
• 布线问题
• 01背包

7题

• 搜索有序表，跳跃表
• n后问题
• 整数因子分解
• 主元素问题
• 素数测试