算法分析与设计
本文最后更新于 2023-10-12，文章内容可能已经过时。
算法设计与分析
1.绪论：
1.1 算法特性：
1.输入
2.输出
3.可行性
4.有穷性（终止性）
5.确定性
1.2 问题与问题实例：
问题是由输入和输出组成的二元组集合，问题实例是其中的一个二元组。
一个算法求解一个问题，而不是问题实例。
1.3 算法正确性：
一个算法是正确的，如果它对于每一个输入都最终停止,而且产生正确的输出.
调试程序不能证明算法正确，只能证明算法有错。
1.3.1 正确性分析：
循环不变量方法：主要结构为循环的算法的正确性证明。
(有点类似数学归纳法)
1.循环初始：即循环开始前，P成立
2.循环步骤：循环体每执行一次之后P仍然成立
3.循环终止：循环结束后，P成立，保证算法正确
1.4 算法复杂性：
分析算法对不同输入所需资源量
1.5 输入的大小：
设Input是问题P的输入集合，P的输入大小是一个函数
F：Input—N，N是正整数集合.通常用size（a）表示。
1.6 时间复杂度：
算法的时间复杂度是对该输入产生结果所需要的原子操作数。
是输入大小的函数t（n）
1.7 空间复杂度：
空间复杂性是对该输入所需要的存储空间的大小。
1.7.1 时间复杂度分析：
把每个原子操作所需要的时间假定为常数。
把程序所有原子操作执行时间的和加起来，作为时间复杂度。
1.7.2 对时间复杂度的理解：
时间复杂性分析并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。
也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也慢了数百倍，或者变慢了数万倍。
如果不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有O(1)的时间复杂度，也称常数级复杂度。
1.8 其他定义：
2.算法分析的数学基础：
2.1 复杂函数的阶：
影响函数运行时间的主导项。
2.1.1 同阶：
用θ表示。
2.1.2 低阶函数集合：
用O表示。
2.1.3 高阶函数集合：
用Ω表示。
前面的作为高、低阶函数，后面带系数的是用希腊字母表示的函数。
2.1.4 三者的关系：
θ表示渐进紧界
O表示渐进上界
Ω表示渐进下界
显然，o是最坏情况，Ω是最好情况，一般来说，很少用Ω描述算法的时间复杂度，一般使用O。
2.1.5 严格低阶函数：
与低阶差不多，但是少了等号。
2.1.6 数学公式中函数阶的定义：
2.2和式的计算和估计：
2.3递归方程：
递归方程是使用具有较小输入值的相同方程来描述一个方程。
有多种解法.
2.3.1 替换方法：
先猜测解，然后用数学归纳法证明。
2.3.2 迭代计算:
通过和式子估计的方式求出结果.
2.3.3 master定理:
3.排序与分治：
3.1 算法设计:
1.边界条件:递归的底层调用的条件.
2.divide:分成多个子问题
是一个划分,根据某种划分条件,把集合划分成几个部分
2.conquer:递归调用正在设计的算法
直接调用当前正在进行的函数即可,返回值肯定是和当前函数的返回值相同.
3.merge:合并子问题的解
划分成几个部分就对几个部分进行合并,要注意,合并的结果就是当前函数的返回值,也就是conquer的返回值,根据不同的问题,合并的具体逻辑也不相同.
3.2 例1:求max,min
简单来说就是通过递归,把运算划归到两个两个数进行运算.
终止条件:
只剩两个数的时候比较,后返回
divide:
根据数组中点分成两个部分
conquer:
对两个部分分别求max,min
merge:
分别从两个max,min中找到max,min.
3.3 例2:快速排序
划分成两个部分,分别排序,然后在合并起来.
快速排序:
终止条件:
只剩两个数,直接返回
divide:
选定一个数,把一个数组分成三部分:p左边的都比p小,p右边的都比p大.
couquer:
对这两个数组分别使用快速排序.
merge:
不需要merge,递归的运算完成之后就已经是排序完成了.
时间复杂度:
注意:此处的时间复杂度是用θ表示的,也就是说,这是一个稳定的算法,不会因为数据排列方式的不同而不同.
而那些用o来表示的,可以说是不稳定算法,代表了最差的复杂度.
3.4 排序问题的下界:
意义:
3.5 例子3:一维空间:
divide:
折半把点分成两部分.
conquer:
对两部分别求最近的两个点
merge:
在两个集合合并的时候,通过边界条件求出最近的两个点.
3.6 循环不变量方法:
4.动态规划:
4.1 分治算法的问题:
分治算法是把原始问题分解成多个子问题,然后再合并起来.
在分治算法中,子问题之间是相互独立的,也就是说,执行这些子问题的方式不同,得到的结果都是相同的.(比如在数组里面插入)
但是对于有些问题,求解子问题的顺序不同会导致结果不同,这样就不能使用分治算法了.
4.2 优化问题:
问题可能有很多解，每个可能的解都对应有一个值，这个值通常称为代价.
优化问题是要在该问题所有可能的解中找到具有最优值(最大/最小)的解，即问题的一个最优解.
一个问题的最优解不一定是唯一的.举例：最短路径，旅行商、任务调度等问题.
因此我们也可以说：优化问题就是给定一个代价函数，在问题的解空间中搜索具有最小或最大代价的优化解.
动态规划是解决优化问题的一种常见方法.
简单来说,优化问题要经过很多个决策,从而得到最终的结果,最优化问题一般是让我们求解这些”决策”,即求解决策变量,而动态规划的算法题则主要让我们根据这些决策求解出最终的结果.
4.3 动态规划简介:
Dynamic Programming ,称为DP.
把原始问题划分成一系列子问题.
不同子问题的数目常常只有多项式量级.
求解每个子问题仅一次，并将其结果保存在一个表中，以后用到时直接存取，不重复计算，节省计算时间.
自底向上地求解子问题.
一类优化问题：可分为多个相关子问题，子问题的解被重复使用.
4.3.1 优化子结构:
当一个问题的优化解包含了子问题的优化解时，我们说这
个问题具有优化子结构。
子问题是指数据量比较小的原始问题.这句话的意思是,原始问题的解中,属于子问题这一小部分的值放到子问题里面,依旧是最优解.
举个例子,比如最短路径问题,求a到b的最短路径,他的一个子问题是求a到c的最短路径,设x为最优解,那么x中从a到c的解也一定是这段路径上的最优解.否则x不可能成为最优解.
(其实就是反证法)
4.3.2 重叠子问题:
在问题的求解过程中，很多子问题的解将被多次使用.
也就是说可以通过之前的状态得出之后的状态.即可以使用递推方程求解.
4.4 过程:
1.分析最优解的结构
2.递归的定义最优解的代价
3.递归地划分子问题
4.自底向上计算优化解的代价，记录优化解的构造信息
5.构造优化解
这个过程实在是过于抽象了,下面试图给出一种自己的过程:
4.4.1 证明动态规划:
即验证这个问题具有优化子结构和重叠子问题的特征.
4.4.2 数学的定义原问题和子问题:
子问题是数量更小的原始问题.
切记,在子问题定义时,涉及到当前决策一定要进行说明,否则会导致递推方程出现错误.
比如在”打家劫舍”问题中,定义dp数组时一定要加上限定条件:是否已经盗窃了当前房屋.即对当前问题作出决策.
4.4.3 写出递归方程:
4.4.4 求解:
4.5 例子1:最长公共子序列:
是在做一种选择,对每一个元素,选择要不要这个元素.
核心递归方程:
| |
O(ij).
4.6 例子2:背包问题:
4.7 例子3: 三角形路径问题:
5.贪心算法：
5.1 简介：
贪心算法总是做出在当前来看最好的选择。
并不从整体最优考虑，做出的只是在某种意义上的局部最优解。
希望通过作出局部优化选择达到全局优化选择。
贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解，如：单源最短路经问题、最小生成树问题等
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
是在最优化问题的决策的过程中,针对如何决策所进行的算法.
5.2 产生优化解的条件：
5.2.1.优化子结构：
若一个优化问题的优化解包含它的(剩余)子问题的优化解，则称其具有优化子结构。
最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，我们可以通过子问题的最优解，推导出问题的最优解。如果我们把最优子结构，对应到我们前面定义的动态规划问题模型上，那我们也可以理解为，后面阶段的状态可以通过前面状态推导出来。
5.2.2 Greedy选择性(Greedy-choice property)：
一个优化问题的全局优化解可以通过局部优化选择
得到。
greedy选择性证明：
简单来说,是针对一个全局最优解进行分析,最好对这个全局最优解进行排序.
然后取出其中一个,与贪心算法所取出的那一个进行比较.
有两种情况:
1.是同一个:符合贪心算法要求
2.不是同一个:则使用剪枝粘贴技术,即把当前这个去掉,然后加上贪心的这一个,然后证明新的这个解是比原来的最优解更优秀的一个解.
用这两点证明贪心算法可以得到最优秀的解.
5.3 与动态规划的比较：
最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。
贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。
动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。
而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。
5.4 设计贪心算法的步骤：
1.设计贪心选择方法：
2.证明方法的优化子结构和选择性
3.设计算法
5.5 最小生成树：
5.5.1 kruskal算法：
每次找一条权值最小的边加入集合。
5.5.2 prim算法：
每次找两个点集合之间连接的边里面，权值最小的加入边集合，同时把点加入点集合.
6.平摊分析：
6.1 简介：
目的是分析给定数据结构上的n个操作的上界.
6.2 聚集方法：
目的是分析n个操作系列中每个操作的复杂性上界。
6.3 栈操作：
6.3.1 基本操作：
6.3.2 操作分析：
7.树搜索：
7.1 概述:
简单来说,就是把问题的数据集合放在树中,运用树搜索的相关知识和方法解决问题.
7.2 相关搜索方法:
7.2.1 DFS:
深度优先搜索.
7.2.2 BFS:
广度优先搜索.
7.2.3 爬山算法:
贪心算法加深度优先搜索.
在选择哪个节点开始深度优先搜索时,使用评估函数,不同的问题评估函数不一样.根据不同节点的评估函数的值确定搜索的先后顺序.
具有局部优化的特征.
7.2.4 Best-First算法:
贪心算法加广度优先搜索.
在针对哪些节点开始广度优先搜索时,同样是使用函数进行评估,对函数小(大)的节点进行广度优先搜索.函数值相同的节点都要进行搜索.
具有全局优化的特征.(其实广度优先搜索本事具有这种特征).
7.2.5 分支限界算法:
同样是对广度优先搜索的一种优化.
分支限界法的步骤如下：
1)按宽度优先策略遍历解空间树
2)在遍历过程中，对处理的每个结点i，根据界限函数，估计沿该结点向下搜索所可能达到的完全解的目标函数的可能取值范围—界限bound(i)=[dow(i), up(i)]
从中选择使目标函数取的极小值的结点优先进行宽度优先搜索，从而不断调整搜索方向，尽快找到问题解。
在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。
8.图算法:
8.1 最大流:
8.1.1 问题概述:
8.1.2 解题思路:
8.1.2.1 最大流等于最小割:
过桥可以很简单的理解.
8.1.2.2 ford-fulkerson算法:
1.选定一个流(注意流和流网络的不同之处,流网络只有最大容量,流除了容量还有余量)
2.根据这个流找到残留网络
3.根据残留网络找到增广路径
若一条路径上的残余容量大于0,那么这就是一条增广路径.
4.在增广路径上压入新的流量,形成新的流,然后重复2.
5.结束:直到找不到增广路径为止.得到的流就是最大流.
8.2 单源最短路:
\Dijkstra(迪杰斯特拉)算法是计算单源最短路径算法，用于计算一个结点到其他所有结点的最短路径。
该算法以源点为起始点，不断更新其他点到已经确定距离结点的距离，选取距离最小的结点加入S集合，直到S集合存放有所有的结点.
步骤:
现在一张图中有n个结点，有两个集合，S集合和V集合。S集合表示已经选取的结点，V集合表示还没有选取的结点
1.计算原点到各点的距离.不能直接到达的空着.
2.选取1中距离最小的点加入s集合
3.计算经过新加入的点,到其他各个点的距离
4.取距离里面最小的,把那个点加入s集合.
……
不断重复,直到s中包含所有点为止.
算法复杂度o(n2).
