高级算法复习指南

自用 如果帮到了你就点个关注和赞吧！

1.算法知识回顾

求两个不全为0的非负整数m和n的最大公约数

数据结构回顾

数组

连续内存分配、静态大小、类型一致、索引访问、访问时间相同、边界检查

多维数组：数组的数组，可以是连续的，也可以是分块的，取决于语言实现

动态数组：如Java ArrayList

耗时的操作：插入和删除——分配新空间、复制数据

链表

数据＋指针

不一定连续存储，动态大小，快速的插入和删除操作

单向链表、双向链表、循环链表、双向循环链表

但需要维护额外的链接（指针）的空间

随机访问数据的开销大（查找、更新）：从拿到的指针开始寻找

栈

后进先出，Last In First Out, LIFO原则

基于数组（顺序栈）：每个操作都是O(1)的运行时间；但是可能空间浪费或不足

基于链表（链式栈）：操作稍复杂，但是不需要考虑空间问题

Push, Pop, Top, IsEmpty, Size

括号匹配：在编译器中用于检查括号是否正确匹配。

后缀表达式求值：后缀表达式（逆波兰表达式）可以通过栈来高效地求值。

函数调用栈：在程序执行时，每个函数的调用信息（如返回地址、局部变量等）都保存在栈中。

表达式转换：将中缀表达式转换为后缀表达式或前缀表达式。

深度优先搜索（DFS）：在图算法中，栈用于存储待访问的节点

队列

先进先出，First In First Out, FIFO原则

enqueuer(o)：在队列尾部插入对象

dequeuer()：删除并返回队列头部的对象；如果队列为空，则发生错误

图

G＝<V,E>：结点或者顶点（节点），边（弧线、连接）

边分为有向的和无向的：节点对(u,v)是有序的或无序的；无向图，有向图，混合图

类之间的关系——有向图

城市地图——混合图：单行道路、双向道路

有向边：端点为始点、终点；相邻的节点；边和点关联；节点的入边、出边、入度、出度

图的相关算法：

深度优先搜索（DFS）：从一个节点开始，递归地访问所有未访问的邻接节点。

广度优先搜索（BFS）：从一个节点开始，按层访问所有邻接节点。

最短路径算法：如Dijkstra算法、Floyd-Warshall算法等，用于计算图中两点之间的最短路径。

最小生成树算法：如Prim算法、Kruskal算法等，用于在无环图中找到连接所有节点的最小权重边的子集。

连通性算法：用于检查图中是否存在从一个节点到另一个节点的路径。

网络流算法：用于解决网络中的最大流、最小费用流等问题。

树

除了根，每个节点有一个父亲、0个或多个孩子元素

叶子节点：没有孩子节点

树的相关算法：

B树构造，节点的插入、删除

哈夫曼编码：使用哈夫曼树进行数据压缩。

最小生成树：在无向图中找到连接所有节点的最小权重边的子集

最优二叉查找树生成

集合，字典（HashMap）

2.蛮力法

选择排序

遍历列表，找到最大或最小的与第一个没有排序好的交换

时间复杂度O(n^2)

冒泡排序

遍历列表，每次都把与当前元素与下一个是逆序的元素交换，把最大或最小的元素排到最后

时间复杂度O(n^2)

凸集合

定义：对于平面上的一个点集合（有限的或者无限的），如果以集合中任意两点P和Q为端点的线段都属于该集合，我们说这个集合是凸的

凸集合例子：直线、三角形和任意凸多边形等

非凸集合例子：五角星、月牙形状等

凸包

一个点集合S的凸包是包含S的最小凸集合（“最小”是意指，S的凸包一定是所有包含S的凸集合的子集）

例子

如果S是凸的，它的凸包是它本身

如果S只有两个点、如果S只有三个共线的点、如果S只有三个不共线的点

凸包定理

任意包含多于两个不共线点的集合S的凸包肯定是以S中某些点为顶点的凸多边形

旅行商问题

背包问题

一个大小为10的背包，装入大小和价值为（7，42），（3，12），（4，40）和（5，25）的四个物品，如何装使得装入物品价值最大

分配问题

将n个任务分配给n个人执行，每个人只执行一个任务，每个任务只能给一个人执行；将第j个任务分配给第i个人执行的成本是C[i,j]；如何找到总成本最小的分配方案？

匈牙利算法

1. 构造成本矩阵
2. 每行、每列减去最小值
3. 以每一个独立的0画十字，已经在线上的0不独立
4. 如果十字可以覆盖所有的行和列，则已经存在最优解，即每行、列找到一个独立的0，对应的位置为最优解（使用最少的直线覆盖所有0，如果直线数目<n则没有达到最优）；否则则进行下一步
5. 用最少的直线覆盖所有0；没有被直线覆盖的区域每行减去区域内最小值，再执行覆盖区域每列加上该最小值，回到第3步

详细可以参考匈牙利算法详解-CSDN博客

个人觉得ppt里的例子没说明白

直接计算N！

3.思想

蛮力法、暴力法

算法思想

是一种简单直接地解决问题的方法，直接基于问题的描述和涉及的概念

唯一一个能够应用于所有问题的策略

肯定会给出一种对应的解，不受数据规模的限制

可能比设计一个好的算法需要更少的时间

给出一个问题解的时间复杂度上界，衡量其它算法的时间效率

选择排序：每次遍历未排序的整个列表，选择一个最小的与第一个没有被交换的进行交换，下一次从被交换的下一个元素开始遍历。

比较次数：n(n-1)/2

冒泡排序：从第一个元素开始遍历列表直到不确定位置的最后一个元素，如果相邻元素是逆序则交换位置；每一次遍历后，有一个元素被放到对应的位置上。

比较次数：n(n-1)/2

求一个数值数组中大小最接近的两个元素的差的算法

遍历一遍数组，求出相邻两个元素差的绝对值

改良版 先对数组进行排序 再求差值的最小值

凸包问题

凸包问题（convex-hull problem）是为一个有n个点的集合构造凸包的问题。

蛮力法的解决方式：对于一个𝑛个点集合中的两个点𝑝𝑖和 𝑝𝑗 ，当且仅当该集合中的其他点都位于穿过这两点的直线的同一边时，他们的连线是该集合凸包边界的一部分。对每一对点都做一遍检验之后，满足条件的线段构成了该凸包的边界。最终，构成凸包边界的所有线段的两端点即为凸包的极点。

分治法

算法思想

将问题实例划分为同一个问题的几个较小实例，最好拥有相同规模

对每一个较小规模的实例进行求解

如果需要则以某种方式合并这些小问题的解得到原问题的解

合并排序

通过元素的位置对他们进行分组

时间复杂度O(nlogn)

快速排序

通过元素的值对他们进行分组

public class QuickSort {  // 快速排序主方法  public static void quickSort(int[] arr, int left, int right) {  if (left < right) {  // 划分操作  int pivotIndex = partition(arr, left, right);  // 对pivot左右两边的子序列递归进行快速排序  quickSort(arr, left, pivotIndex - 1);  quickSort(arr, pivotIndex + 1, right);  }  }  // 划分操作  private static int partition(int[] arr, int left, int right) {  // 选取基准值（这里选择最右边的元素作为基准值）  int pivot = arr[right];  int i = left - 1; // 小于基准值的元素的索引  for (int j = left; j < right; j++) {  // 如果当前元素小于或等于基准值  if (arr[j] <= pivot) {  i++; // 增加i  // 交换arr[i]和arr[j]  swap(arr, i, j);  }  }  // 将基准值交换到它最终的位置  swap(arr, i + 1, right);  return i + 1;  }  // 交换数组中两个元素的位置  private static void swap(int[] arr, int i, int j) {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;  }  
}

时间复杂度O(nlogn)

最近对问题

import java.util.Arrays;  
import java.util.Comparator;  static class Point {  double x, y;  public Point(double x, double y) {  this.x = x;  this.y = y;  }  
}  // 计算两点之间的距离的平方  
public static double distanceSquared(Point p1, Point p2) {  return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);  
}  // 分治法求解最近对问题  
public static double closestPair(Point[] points) {  if (points.length < 2) {  return Double.POSITIVE_INFINITY; // 没有或只有一个点，返回无穷大  }  // 根据x坐标排序  Arrays.sort(points, Comparator.comparingDouble(p -> p.x));  // 然后根据y坐标排序Arrays.sort(points, Comparator.comparingDouble(p -> p.y));// 调用递归函数  return Math.sqrt(closestPairRecursive(points, 0, points.length - 1));  
}  // 分治递归函数  
private static double closestPairRecursive(Point[] points, int l, int r) {  if (l == r) {  return Double.POSITIVE_INFINITY; // 只有一个点，返回无穷大  }  if (l == r - 1) {  return distanceSquared(points[l], points[r]); // 两个点，直接计算距离  }  int n = r - l + 1;  if (n <= 3) {  // 如果点的数量小于等于3，则直接计算最小距离  double minDist = Double.POSITIVE_INFINITY;  for (int i = l; i < r; i++) {  for (int j = i + 1; j <= r; j++) {  minDist = Math.min(minDist, distanceSquared(points[i], points[j]));  }  }  return minDist;  }  // 分治步骤  int mid = l + (r - l) / 2;  double dl = closestPairRecursive(points, l, mid);  double dr = closestPairRecursive(points, mid + 1, r);  double d = Math.min(dl, dr);  // 合并步骤，找出跨左右子集的最小距离  Point[] strip = new Point[n];  int j = 0;  for (int i = l; i <= r; i++) {  if (Math.abs(points[i].x - points[mid].x) < d) {  strip[j++] = points[i];  }  }  // 按y坐标对strip中的点进行排序  Arrays.sort(strip, 0, j, Comparator.comparingDouble(p -> p.y));  // 在strip中查找最小距离  for (int i = 0; i < j; i++) {  for (int k = i + 1; k < Math.min(j, i + (int)(d / strip[i].y + 1)) && (strip[k].y - strip[i].y) < d; k++) {  d = Math.min(d, distanceSquared(strip[i], strip[k]));  }

凸包问题

public class Point {  public double x;  public double y;  public Point(double x, double y) {  this.x = x;  this.y = y;  }  
}  public class ConvexHull {  // 计算叉积  public static double crossProduct(Point p1, Point p2, Point p3) {  return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);  }  // 使用蛮力法计算凸包的极点  public static List<Point> bruteForceConvexHull(List<Point> points) {  int n = points.size();  if (n < 3) {  // 如果点的数量少于 3 个，则这些点就是凸包的极点  return points;  }  List<Point> hull = new ArrayList<>(); // 用于存储凸包的极点  for (int i = 0; i < n; i++) {  for (int j = i + 1; j < n; j++) {  // 遍历每一对点 (i, j)  int left = 0; // 用于计数点在直线的左侧  int right = 0; // 用于计数点在直线的右侧  for (int k = 0; k < n; k++) {  if (k == i || k == j) {  // 跳过当前对点  continue;  }  double cp = crossProduct(points.get(i), points.get(j), points.get(k));  if (cp > 0) {  left++; // 点在直线的左侧  } else if (cp < 0) {  right++; // 点在直线的右侧  }  }  if (left == 0 || right == 0) {  // 如果所有点都在直线的一侧，则 (i, j) 是凸包的边  if (!hull.contains(points.get(i))) {  hull.add(points.get(i));  }  if (!hull.contains(points.get(j))) {  hull.add(points.get(j));  }  }  }  }  return hull;  }  

减治法

算法思想

利用一个问题给定实例的解和同样问题较小实例的解之间的某种关系，将一个大规模的问题逐步化简为一个小规模的问题

和分治法之间的区别和联系？

分治：是多个小问题，小问题之间的联系

减治：还是一个小问题，小问题与原问题之间的联系

例：插入排序

变治法

算法思想

通过转换问题使得原问题更容易求解

实例化简

改变表现

问题化简

时空权衡

算法思想

空间换时间

字符串匹配

Horspool提出的简化版

根据文本中对齐模式最后一个字符的字符c的不同情况确定移动的距离：

情况1：模式中不存在c，模式安全移动的幅度就是它的全部长度

情况2：模式中存在c，但它不是模式的最后一个字符，移动时应该把模式中最右边的c和文本中的c对齐

情况3：c正好是模式的最后一个字符，但是在模式的其他字符中不包含c，移动的情况：移动幅度等于模式长度m

情况4：c正好是模式的最后一个字符，而且在模式的前m-1个字符中包含c，移动的情况：把模式中前m-1个字符中的c和文本中的c对齐

代码实现

import java.util.HashMap;public class Horspool {public static int horspool(String text, String pattern) {int n = text.length();int m = pattern.length();if (m == 0) {return 0;}HashMap<Character, Integer> last = new HashMap<Character, Integer>();for (int k = 0; k < m; k++) {last.put(pattern.charAt(k), k);}int i = m - 1;int k = m - 1;while (i < n) {if (text.charAt(i) == pattern.charAt(k)) {if (k == 0) {return i;} else {i -= 1;k -= 1;}} else {int j = last.containsKey(text.charAt(i)) ? last.get(text.charAt(i)) : -1;i += m - Math.min(k, j + 1);k = m - 1;}}return -1;}public static void main(String[] args) {String text = "hi hold world";String pattern1 = "world";System.out.println(horspool(text, pattern1));String pattern2 = "python";System.out.println(horspool(text, pattern2));}
}

Boyer-Moore算法

class BmAlgorithm {private final static int ASCII_SIZE = 256;public static int bmSearch(String s, String t) {int n = s.length();int m = t.length();if (m == 0) {return 0;}//坏字符规则表 badTable: 记录模式串中每个字符最后出现的位置int[] badTable = new int[ASCII_SIZE];Arrays.fill(badTable, -1);for (int i = 0; i < t.length(); i++) {badTable[t.charAt(i)] = i;}/** 好后缀规则表 goodTable: 用数组 suffix 表示* suffix[i] 表示长度为 i 的好后缀匹配的最长靠右子串的起始位置* */int[] suffix = new int[m];Arrays.fill(suffix, -1);for (int i = 0; i < m - 1; i++) {int j = i;int k = 0;while (j >= 0 && t.charAt(j) == t.charAt(m - 1 - k)) {j--;k++;suffix[k] = j + 1;}}int i = 0;while (i <= n - m) {//从右往左开始匹配int j = m - 1;while (j >= 0 && t.charAt(j) == s.charAt(i + j)) {j--;}if (j < 0) {//匹配成功return i;} else {//根据坏字符规则计算要移动的位数int badShift = j - badTable[s.charAt(i + j)];//根据好字符规则计算要移动的位数int goodShift = 0;//如果 j == m - 1，即好后缀为 ""，此时需要遵循坏字符规则if (j < m - 1) {goodShift = moveByGs(j, m, suffix);}i += Math.max(badShift, goodShift);}}//无法匹配return -1;}private static int moveByGs(int j, int m, int[] suffix) {// k 为当前好后缀 pattern[j + 1...m - 1] 的长度int k = m - 1 - j;if (suffix[k] != -1) {//好后缀可以直接匹配return j - suffix[k] + 1;}//好后缀不能直接匹配，那么寻找与好后缀的后缀子串匹配的模式串的最长前缀for (int r = j + 2; r <= m - 1; r++) {//判断后缀子串 pattern[r...m - 1] 匹配的最长靠右子串的起始位置是否为 0if (suffix[m - r] == 0) {return r;}}//上面两种情况都没有匹配成功，则直接返回模式串的长度return m;}
}

B树

索引技术

一种利用额外空间提高对给定大规模数据集合访问速度的数据组织技术

Hash也是一种索引技术

对2-3树的扩展（允许查找树的一个节点中包含多个键）

所有的数据记录（或者键）都按照键的升序存储在叶子中；它们的父母节点作为索引

每个父母节点包含n-1个有序的键K1<…<Kn-1，称为n节点

这些键之间有n个指向子女的指针，使得子树T0中的所有键都小于K1，子树T1中的大于等于K1小于K2，以此类推

对于任何包含n个元素、次数为m、高度为h>0的B树来说，有

4.贪心法

思想

通过一系列步骤构造问题的解，每一步对目前构造的部分解作一个扩展，直到获得问题的完整解。

特点

可行性：必须满足问题的约束——从给定的面值中选择组成比剩余金额小的数值

局部最优：当前已经有的部分解情况下，在当前步骤的所有可行选择中选择最佳——局部最佳

不可取消：选择一旦作出，进入下一个步骤后，之前的选择不可取消

最小生成树算法

最小生成树问题的定义:连通图的一棵生成树是包含图的所有顶点的连通无环子图，也就是一棵树。加权连通图的一棵最小生成树是其权重最小的生成树，其中，树的权重定义为所有边的权重总和。

最小生成树问题就是求一个给定的加权连通图的最小生成树问题。

1.Prim算法

算法流程：

第一步：设图中所有顶点的集合为V，u代表已经加入最小生成树的顶点的集合，v代表未加入最小生成树的顶点的集合，最由于从某点s开始，因此u={s}，v={V-u}

第二步：在两个集合u,v中选择一条代价最小的边，将在v中连接这条边的那个顶点x加入到最小生成树顶点集合u中，并且更新与x相连的所有邻接点

第三步：重复上述步骤，直到最小生成树顶点集合u中有n个顶点为止

参考原文链接：最小生成树算法之Prim(普里姆)算法_最小生成树prim算法-CSDN博客

2.Kruskal算法

算法流程：

对所有的边按照权值排序，不停的加入权值最小的边，如果加入的边导致了回路，则跳过，直到所有顶点都加入

参考原文链接：数据结构C++——最小生成树之Prim算法和Kruskal算法_krusal算法图解-CSDN博客

任务相容

贪心策略——按结束时间从小到大选择活动

我们将活动按照截止时间从小到大排序（即上表），然后从前向后选择，只要当前活动与前面所选的活动相容（时间不冲突），就将该项目加入集合A.

选择活动1，截止时间最早：活动2、3皆与活动1不容，活动4与活动1相容；

选择活动4：活动5、6、7皆与活动4不容，活动8与活动4相容；

选择活动8：活动9与活动4不容，活动10与活动1、4、8皆不相容。

参考原文链接：12贪心法——活动安排相容问题_贪心法活动安排 ppt-CSDN博客

5.动态规划

最长公共子序列

例题描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

num[i][j]的含义：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为num[i][j]

递推关系式

代码实现

最长回文子序列

递推关系式

矩阵连乘

例题描述：A是一个p × q矩阵，B是一个q × r矩阵，AB相乘，得到的矩阵元素个数为p × r，每个元素由q次乘法得到，因此所需乘法次数为p × q × r。

在计算矩阵连乘积时，加括号的方式对计算量有影响。

例如有三个矩阵A1,A2,A3连乘，它们的维数分别为

10x100，100×5，5×50。用第一种加括号方式(A1A2)A3计算，则所需数乘次数为

10×100×5＋ 10×5×50 = 7500。用第二种加括号方式A1(A2A3)计算，需要

100×5×50+10×100 x50=75000次数乘

递推公式

代码实现

public static void matrixChain(int [] p, int [][] m, int [][] s){int n=p.length-1;for (int i = 1; i <= n; i++) m[i][i] = 0;for (int r = 2; r <= n; r++)for (int i = 1; i <= n-r+1; i++) {int j=i+r-1;m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];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;}}}} 

原文链接：动态规划：矩阵连乘问题（文末附有手写版例题）-CSDN博客

6.平滑函数和主定理

平滑函数：定义在自然数集上的一个非负的最终非减函数。

主定理

7.复杂度的表示法

O(f) - 大O表示法

• 含义：给出了算法运行时间的上界，也就是最坏情况下的时间复杂度。
• 性质：

• • 与具体的常系数无关：O(n)和O(2n)表示的是同样的复杂度。
  • 多项式级的复杂度相加时，选择高者作为结果：O(n²)+O(n)和O(n²)表示的是同样的复杂度。
  • 存在大于0的常数c和非负整数n₀，使得：对于所有的n>=n₀来说，t(n)<=cg(n)

Ω(f) - 大Ω表示法

• 含义：给出了算法运行时间的下界，也就是最好情况下的时间复杂度。
• 性质：与O(f)相对，表示算法运行时间的最低可能复杂度。
• 存在大于0的常数c和非负整数n₀，使得：对于所有的n>=n₀来说，t(n)>=cg(n)

Θ(f) - 大Θ表示法

• 含义：给出了算法运行时间的上界和下界，即算法运行时间的确界。
• 性质：当且仅当f(n)同时是算法的上界和下界时，使用Θ(f)表示。

• • 并非所有算法都有Θ(f)表示法，因为有些算法的上界和下界可能不同。
  • 存在大于的常数c₁,c₂，和非负整数n₀，使得：对于所有的n>=n₀来说，c₂g(n)<=t(n)<=c₁g(n)

补充

性质：传递性，加法和乘法

8.近似算法

近似算法的定义及评价近似算法的好坏

近似比≥1

First Fit Algorithm(FF)

First fit策略的精髓在于寻找当前物品所能存放的第一个箱子。First fit以物品为视角，在处理当前物品i时，首先寻找第一个还没有装满的箱子j。若箱子j可以装下物品i，则将物品i装入箱子j后，继续处理下一个物品i+1；若箱子j装不下物品i，则考虑下一个箱子j+1，直至为物品i找到能存放的箱子。后续物品依上述描述继续处理。当然，若某个箱子已经装满，则该箱子后续就不能再装入任何物品，即将其彻底关闭；若当前已经装入物品的箱子都不能装下物品i，则会将物品i放入一个未被使用过的新箱子。

时间复杂度O(n^2)

Next Fit Algorithm(NF)

Next fit策略的精髓在于为当前待装入物品的箱子寻找可以装入的物品。不同于其它三种策略，Next fit策略以箱子为视角，在处理箱子j时，首先判断当前待装入的物品i能否装入箱子j。若能装入，则继续处理下一个物品i+1；若不能装入，则关闭箱子j，转而打开箱子j+1。后续物品依上述描述继续处理。很明显，Next fit策略的速度极快，它省去了很多判断的步骤，但是它的性能同时也是极差的。

时间复杂度O(n)

参考文章链接：基于近似算法求解装箱问题的研究-CSDN博客

First Fit Decreasing(FFD)

First Fit Decreasing的策略（算法流程）：

1.对物品的体积进行降序排列

2.依次考虑每个物品，放入能容纳他们的第一个箱子

3.如果没有箱子能容纳该物品，则开一个新箱子用于存放物品

对物品大小进行降序排列 时间复杂度O(nlogn)

降序之后进行首次适应算法 时间复杂度O(n^2)

在线算法

在线算法的定义

定义： 在线算法是一种在接收到输入数据时立即处理它们的算法。这些算法在每一步都必须做出决定，而不知道未来的输入。

First FIt(FF)和Next Fit(NF)是在线算法

9.NP和NPC理论

理论

P类问题：可以在多项式时间内解决的问题。

NP问题：可以在多项式时间内验证解是否正确的问题。

NP-hard问题：所有的NP问题都可以在多项式时间内归约到这个问题的难度级别。

NP-完全问题：既属于NP类问题，又属于NP-hard问题。如果可以在多项式时间内找到一个NP完全问题的解，那么多项式时间内，所有NP问题都可以得到解答。

实际价值

理解问题的复杂性

指导算法设计

优化计算资源

0-1背包证明