文章目录
  1. 1. 算法设计与分析 笔记
    1. 1.1. 递归分治和动态规划
      1. 1.1.1. 大整数乘法,分治降低复杂度 P19
      2. 1.1.2. Strassen矩阵乘法 P19
      3. 1.1.3. 棋盘覆盖 P20
      4. 1.1.4. 归并算法 P22
      5. 1.1.5. 快速排序 P24
      6. 1.1.6. 线性时间选择 P26
      7. 1.1.7. 最接近点对问题 P30
      8. 1.1.8. 循环赛日程表 P35
      9. 1.1.9. 矩阵连乘问题 P45
      10. 1.1.10. 最长公共子序列 P52
      11. 1.1.11. 最大字段和 P54
      12. 1.1.12. 凸多边形最有三角剖分 P59
      13. 1.1.13. 0-1背包问题 P71
      14. 1.1.14. 完全背包
      15. 1.1.15. 多重背包
    2. 1.2. 贪心
      1. 1.2.1. 最优装载问题 P95
      2. 1.2.2. 哈夫曼树 P99
      3. 1.2.3. 最小生成树 P101
    3. 1.3. 回溯法和分支限界法
    4. 1.4. 胜者树、败者树、堆排序

引言:使用电子工业出版社的《计算机算法设计与分析(第四版)》,还记录了一些其他的关于算法的笔记。


算法设计与分析 笔记

递归分治和动态规划

一定要保证

  1. 分解后的问题依然是相同结构的规模更小的子问题

差异:

  1. 递归要求每个子问题相互独立
  2. 动态规划要保证每个子问题相互重叠
  3. 动态规划是最优子结构问题(比相同点的那一条更强)
  4. 动态规划需要无后效性
    • 第一层含义是,在推导后面阶段状态的时候,我们只关心前面阶段的状态值,不关心这个状态是怎么一步步推导出来的。
    • 第二层含义是,某阶段状态一旦确定,就不受之后阶段的决策影响。
    • 无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型,其实基本上都会满足无后效性。

大整数乘法,分治降低复杂度 P19

XY=AC2n+(AD+BC)2n/2+BDXY=AC2^n+(AD+BC)2^{n/2}+BD

需要四次n/2位的乘法(AC、AD、BC、BD),2次位移,3次加法

XY=AC2n+((AB)(DC)+AC+BD)2n/2+BDXY=AC2^n+((A-B)(D-C)+AC+BD)2^{n/2}+BD

将AD+BC换为AD-AC-BD+BC+AC+BD,然后再配方为(A-B)(D-C),这样变成了3次n/2位乘法(AC、(A-B)(D-C)、BD),2次位移,6次加法。

复杂度从O(n2)O(n^2)降低为O(n1.59)O(n^{1.59})

Strassen矩阵乘法 P19

计算两个nxn的矩阵乘积显然是O(n3)O(n^3)的,strassen通过矩阵分块(2x2的分块矩阵),再通过因式分解,将乘法从8次变为7次,因此复杂度降低为O(nlog7)O(n^{log7})

棋盘覆盖 P20

给出覆盖1个点的棋盘(记为污染点),4种L形态的骨牌,通过若干次覆盖,给出覆盖方案。

很显然,将棋盘四切分,必有一个是被污染的棋盘,有三个没被污染的棋盘。将骨牌放在切分点中间,可以使得四个棋盘都被污染,那么将大问题转为相同性质的小问题,用分治可解。

递归出口是,只剩一个2x2的棋盘,其中有一个污染点,那么覆盖剩下三个点即可。

归并算法 P22

没什么好说的

快速排序 P24

没什么好说的

线性时间选择 P26

给定n个乱序元素,要求找出第k小的元素。

第一种方法是使用快排的思想,每轮哨兵所在位置为i,若k<i,则在左边继续递归,否则在右边继续递归(且找第k-i小的元素)。由于每次都舍弃一半,而每轮是O(n)的,根据万能公式,a=1,b=2,k=1,算法平均复杂度O(n)。

第二种方法见P28,中位数坐标系切分法,精华在于在T(n/5)时间内找到中位数(每次问题规模化为1/5,花费O(nlog5)=O(n)时间)。找到中位数后,每次舍弃掉1/4(坐标系),算下来复杂度O(n),但是是最差复杂度O(n),所以比上一个方法好。

最接近点对问题 P30

一维情况:乱序给出n个数,找出数值相差最小的一对。

二维情况:乱序给出n个点,找出欧氏范数最小的一对。

显然一维情况的第一种方法是O(nlogn)排序再O(n)找出,但无法推广至二维。

一维情况另一种方法是分治法,二分之后,找出左边的最接近点对,找出右边的最接近点对,找出分界边缘的一个点对,比较得出总体的最接近点对。根据万能公式,a=b=2,k=1,因此也是O(nlogn),但易于推广至二维。问题在于分割点的选取应使得两边点数尽量相同,那么可以用上面的O(n)的中位数选取法。

二维情况:选取x的中位数m将点集分割到两个集合,对左边和右边分别进行递归计算,最后再计算点对分别位于两个集合的情况。

假设d=min(左边最小距离,右边最小距离),那么以一个左边的点为中心,以d为半径画半圆,可知右边最多有dx2d的矩形区域的点(实际上精确说是半圆区域,但无妨扩大到矩形)会有可能跟该点连线比d小,经过书上的证明,这个矩形区域最多有6个点。因此对左边点集和右边点集按Y坐标排序即可(由于每次都要排序,很多排序是多余的,因此在最开始进行一次预排序就可以了)。

递归下去,递归出口是左边和右边恰各有一个点。

复杂度根据万能公式,a=b=2,k=1。O(nlogn),而排序也是O(nlogn)的,所以总体还是O(nlogn)。

循环赛日程表 P35

12345678八名选手。

先写出

[1221344356657887]\begin{bmatrix} 1&2\\ 2&1\\ 3&4\\ 4&3\\ 5&6\\ 6&5\\ 7&8\\ 8&7\\ \end{bmatrix}

然后把2x2

[1221]\begin{bmatrix} 1&2\\ 2&1\\ \end{bmatrix}

抄送到右下角,把

[3443]\begin{bmatrix} 3&4\\ 4&3\\ \end{bmatrix}

抄送到右上角,下同。

变为:

[12342143341243215678658778568765]\begin{bmatrix} 1&2&3&4\\ 2&1&4&3\\ 3&4&1&2\\ 4&3&2&1\\ 5&6&7&8\\ 6&5&8&7\\ 7&8&5&6\\ 8&7&6&5\\ \end{bmatrix}

然后再4x4,最终:

[1234567821436587341278564321876556781234658721437856341287654321]\begin{bmatrix} 1&2&3&4&5&6&7&8\\ 2&1&4&3&6&5&8&7\\ 3&4&1&2&7&8&5&6\\ 4&3&2&1&8&7&6&5\\ 5&6&7&8&1&2&3&4\\ 6&5&8&7&2&1&4&3\\ 7&8&5&6&3&4&1&2\\ 8&7&6&5&4&3&2&1 \end{bmatrix}

矩阵连乘问题 P45

pxq和qxr的矩阵相乘需要运算pqr次,请给出满足n个矩阵A1A2...AnA_1A_2...A_n连乘次数最短的满足结合律的乘法次序。

显然是具有最优子结构性质,并且有重叠子问题性质的,可以用动态规划求解。

求解n个即求解一个分割点,使得左1,右n-1,或左2,右n-2,或……,或左n-1,右1的分法连乘次数最小。然后再递归下去。

由于有重叠,可以使用记忆递归(备忘录方法)。

最长公共子序列 P52

很简单,看书。

最大字段和 P54

给出一串数字,要求求出使得和最大的数字串。

以k结尾的最大子段和,即要么等于arr[k]+dp[k-1],要么等于arr[k],取决于dp[k-1]是否大于0。

那么以任意k结尾的最大子段和为max(dp[i]),0<=i<len(dp)

滚动求解即可,复杂度O(n)。

分治算法:分为两半,总的最大子段和为左边的最大子段和或右边的最大子段和,或包含中间两个元素的最大子段和。前两种可以递归求解,后一种O(n)求解。最终复杂度由万能公式a=b=2,k=1,最终复杂度O(nlogn)。

凸多边形最有三角剖分 P59

同矩阵连乘问题

0-1背包问题 P71

背包容量为c,那么我可设背包容量0~c一共c+1种状态,每个状态表示该容量的背包所能产生价值的最大值。

可以轻易看出具有最有子结构性质,对每个物品执行“装”和“不装”,都会对某一个状态产生影响,从而优化该状态的最优值。

再看无后效性,如果我们以状态即容量作为外循环,在该状态下,决定一个物品装或不装,从不同的前驱状态转移过来,这样固然是满足无后效性的,但是会导致一个物品可能会被装多次,不合题意。

如果以物品的种类作为外循环,内循环为状态,则相当于已获得n个种类下每个状态的最优背包问题的解,现在新增一个物品种类,求新的解。无后效性满足。但这种情况是否最优子结构呢?我们知道当我在所有容量状态中减去新物品种类的重量后得到的状态集合,已经是减掉了一个或若干个比该重量小的物品的价值了(同时去掉了这些物品),剩下的物品的价值一定使得该容量下价值最优,因此要么从这个状态转移过来,要么就不装,还是采用原来的最优解。所以它是具有子问题重叠性质的。

因此是动态规划问题。

滚动数组怎么优化:我们可以知道出现新物品后,对每个状态的处理需要引用index小的上一轮状态值,因此我们只能从大的index开始往小的更新。

完全背包

完全背包:有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

新加一个物品,要么挤掉一些物品,把该物品放进来(这种说法请参考上述01背包),要么就不放。

和01背包不同的点在于,状态转移是从当前轮转移过来,也就是说有可能引用的某个状态值已经在本轮更新过了(放过该物品了),因此滚动数组的做法是状态也从小的index往大的更新。

多重背包

多重背包:有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

多重背包可以转为01背包问题。

我把n[i]个某物品单独看做n[i]个不同的物品即可转为01背包问题。

另外,多重背包可以用二进制优化,比方说把8可转为1000b,那么通过1000b,100b,10b,1b这四个基数可以表示任意的15以下的数,即可把8个物品压缩到4个物品。

贪心

贪心需要满足:

  1. 最优子结构性质
  2. 贪心选择性质

最优装载问题 P95

有一批集装箱要装上一艘载重量为cc的轮船。其中集装箱ii的重量为wiw_i。最优装载问题要求在装载体积不受限制的情况下,将尽可能多的集装箱装上轮船,注意,不是尽可能重的集装箱

很显然,这是贪心问题,因为假设轻一点的都装不上去,那重一点的更装不上去了。

哈夫曼树 P99

计算WSL的小窍门:对所有非叶结点进行求和即可。

###单源最短路径 P100

Dijkstra:扩充点集。

先计算出原点到各个点的距离,挑距离最短的加入点集,再计算出加入的点相连的边能否使得最短路径更小(原点到该点的最短路径加该点到相连点的距离是否比现存最短路径更小)。

加入集合时,算出的距离即原点到该点的最短路径。

反证法,见P102。

注:要求每条边非负。

最小生成树 P101

Prim算法:扩充点集。

每次挑选集合中能接触到的所有不属于集合的点,选择最短的那一条边(区别于Dijkstra最短路),将点加入集合。重复上一步骤直到有n个顶点。

Kruskal:通过并查集或其他手段,每次连接边的两端不在同一集合的最短的那条边,最终形成n-1条边。

可由离散数学证明,一张n个结点的图如果大于等于n-1条边,则必定只有一个连通分支,或者有多个连通分支,但是成环。如果我们保证不成环,那么一定只有一个连通分支。

回溯法和分支限界法

回溯法使用dfs,分支限界法使用bfs

回溯法找所有解,分支限界法只找一个解

胜者树、败者树、堆排序

堆排序:

在已有元素上建堆或插入元素是自底而上的,取出元素是自顶而下的。

在小顶堆中取出最小元素后,需要将最后一个元素赋值给根节点,然后调整整棵树,此时需要比较两个子结点的大小,取出最小的子结点再和父结点比较,每次下降需要比较两次。

胜者树和败者树:

胜者树如果使用非顺序结构的二叉树实现,需要先获取父结点,随后才能获取兄弟结点,因此需要访存两次(如果使用顺序存储结构,通过数组下标即可定位兄弟结点,此时只需要访存一次)。

败者树由于每次将败者下标放在父结点的数据域,因此当叶结点改变时,只需要比较父结点即可。

在顺序存储结构下,二者优劣性体现在,胜者树需要一路比较一路更新结点,而败者树不一定更新结点,只需要维护一个变量即可,该变量有可能进行寄存器优化。

每次上升只需要比较一次,因此胜者树和败者树比堆排序在时间复杂度的常数上要小,但由于胜者树和败者树只有叶结点存储数据,因此在空间复杂度的常数上比堆排序多一倍。

文章目录
  1. 1. 算法设计与分析 笔记
    1. 1.1. 递归分治和动态规划
      1. 1.1.1. 大整数乘法,分治降低复杂度 P19
      2. 1.1.2. Strassen矩阵乘法 P19
      3. 1.1.3. 棋盘覆盖 P20
      4. 1.1.4. 归并算法 P22
      5. 1.1.5. 快速排序 P24
      6. 1.1.6. 线性时间选择 P26
      7. 1.1.7. 最接近点对问题 P30
      8. 1.1.8. 循环赛日程表 P35
      9. 1.1.9. 矩阵连乘问题 P45
      10. 1.1.10. 最长公共子序列 P52
      11. 1.1.11. 最大字段和 P54
      12. 1.1.12. 凸多边形最有三角剖分 P59
      13. 1.1.13. 0-1背包问题 P71
      14. 1.1.14. 完全背包
      15. 1.1.15. 多重背包
    2. 1.2. 贪心
      1. 1.2.1. 最优装载问题 P95
      2. 1.2.2. 哈夫曼树 P99
      3. 1.2.3. 最小生成树 P101
    3. 1.3. 回溯法和分支限界法
    4. 1.4. 胜者树、败者树、堆排序