笔记-算法设计与分析

type

status

date

slug

summary

01 简介

基本概念

算法的定义：在有限时间内，对问题求解的一个清晰的指令序列。算法的每个输入确定了该算法求解问题的一个实例。

算法的特点：输入，输出，确定性，有穷性和可行性。

算法可以用自然语言或者伪代码表示，或计算机程序实现一个好的算法常常是不懈努力和反复修改的结果。

算法操作的是数据，所以数据结构很重要。

🙄

求gcd：辗转相除法（欧几里得算法、连续整数法）

问题类型

排序问题（稳定、在位）、查找问题（查找键，无全部情况都适合的算法）、字符串处理问题（字符串匹配）、图问题（遍历、最短路径、拓补排序、旅行商、图填色）、组合问题、几何问题（最近邻对问题、凸包问题）、数值问题（解方程、定积分、评估函数）

数据结构

线性数据结构

数组、链表（单双）
堆栈（LIFO）、队列（FIFO）

无向图、有向图、加权图、连通图、无环图、稠密图稀疏图
邻接矩阵、邻接链表

有根树、有序树

集合与字典

02 效率分析基础

算法分析框架

输入规模的度量

选择参数n（input size）

运行时间的度量

基本操作（basic operation）

分析算法效率函数的增长次数

计算在最差、最优和平均情况下的效率

渐进符号

非递归算法分析

输入规模、基本操作、检查依赖、求和表达式、闭合公式

决定用哪个(哪些)参数表示输入规模。

找出算法的基本操作(作为一个规律，它总是位于算法的最内层循环中)。

检查基本操作的执行次数是否只依赖于输入规模。如果它还依赖于一些其他的特性，则最差效率、平均效率以及最优效率(如有必要)需要分别研究。

建立一个算法基本操作执行次数的求和表达式

利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数。

🙄

元素唯一性问题： 采用常规方法的worst cost

先排序后比较

🙄

求矩阵乘法：

时间复杂度：

递归算法分析

输入规模、基本操作、检查依赖、建立递推关系式及初始条件、解递推关系式

决定用哪个(哪些)参数作为输入规模的度量标准。

找出算法的基本操作。

检查一下，对于相同规模的不同输入，基本操作的执行次数是否可能不同。如果有这种可能，则必须对最差效率、平均效率以及最优效率做单独研究。

对于算法基本操作的执行次数，建立一个递推关系以及相应的初始条件。

解这个递推式，或者至少确定它的解的增长次数。

🙄

计算十进制正整数的二进制表达的位数：

平滑法则：

03 蛮力法

蛮力法定义：是一种简单直接地解决问题的方法，通常直接基于问题的描述和所涉及的概念定义。

蛮力法的优点：广泛适用性和简单性；蛮力法的缺点：大多效率低。

蛮力法一般是得到一个算法，为设计改进算法提供比较依据。

穷举法是蛮力法之一，包括旅行商问题（列出所有情况，），背包问题（）和指派问题（）。

选择排序与冒泡排序

排序（降序）：选择排序（每次放到最前面）与冒泡排序（从前往后）均为蛮力法

顺序查找与字符串匹配

04 减治法

减治法定义：利用一个问题给定实例的解和同样问题较小实例的解之间的某种关系，之后可以自顶向下或者自底向上（从小到大，增量法，迭代实现）的方式运用此关系进行求解。

减治法的三种变化形式：

减去一个常量（如每次减一）

减去一个常量因子（如每次减半）

减去的规模是可变的（每次减小的规模不同）：如欧几里得算法

插入排序

🙄

插入排序：

调整使得该指针前面的值均为比它小的值；每一次获得一个较小规模的解，并试用其性质获得一个在较大规模下成立的解。

最坏情况：逆序排列；最好情况：顺序排列

🙄

有向无环图（DAG）的拓补排序： （1）DFS（深度优先查找）：使用栈，先将其全部入栈（入栈时改变入度），每次将入度为0的放进栈中，最后将栈中元素全部弹出，再将弹出结果逆序即可获得拓补排序序列。（2）基于减治技术：每次删掉一个入度为0的顶点，直到只剩下一个源。

🙄

假币问题（n枚硬币中一枚假币）：折半查找俄氏乘法

约瑟夫问题（每轮杀掉偶数编号的人）： J(2k)=2J(k)+1，J(2k+1)=2J(k)+1

05 分治法

分治法是一种一般性的算法设计技术，他将问题的实例划分为若干个较小的实例(最好拥有相同的规模)，对这些小的问题求解，然后合并这些解，得到原始问题的解。

步骤：（分解+递归+合并） ① 将问题划分为两个或更小的子问题； ② 通过递归求解来解决子问题； ③ 将子问题的解合并到原问题的解中

通用分治递推式与主定理

合并排序

快速排序

可以的改进：子数组足够小时采用插入排序；三路划分

🙄

大整数乘法 a=a1a0, b=b1b0, c1=(a1+a0)*(b1+b0)-(c2+c0)

n表示数据的位数（基操：乘法+加法）

也可以用反向替换法求解

🙄

Strassen矩阵乘法通过增加加法的次数减少乘法的次数

🙄

棋盘覆盖问题：

06 变治法

变治法定义：是一种基于变换思想，把问题变换成一种更容易解决的类型。

变治法的三种类型：

实例化简：变换为同样问题的一个更简单或者更方便的实例 改变表现：变换为同样实例的不同表现 问题化简：变换为另一个问题的实例，而这种问题是已知的

预排序

先对序列进行排序（复杂度为），再进行后续操作

检验数组元素的唯一性

模式计算（找数字列表中出现次数最多的数字）

查找某个元素

高斯消去法

前向消去法（获得上三角）：O()

反向替换法（将x的值带入求解出来）：O()

LU分解

解方程组Ax=b等价于解方程组LUx=b。后面这个方程组可以这样解：设y=Ux，那么Ly=b。先解方程组Ly=b,这很容易解，因为L是一个下三角矩阵。然后解方程组Ux = y,用上三角矩阵U来求出x。

求矩阵的逆

计算行列式

堆排序

优先队列：包含操作：① 找出一个具有最高优先级的元素(即最大元素)。② 删除一个具有最高优先级的元素。③ 添加一个元素到集合中。

堆：完全二叉树，最小堆、最大堆

插入：自底向上堆构造

删除：先与最下面的（最后一个键）交换，再自顶向下的调整

堆排序在排列好堆中的数组元素后，再从剩余堆中连续删除最大的元素。在最差以及平均情况下，该算法都属于在位的排序算法，时间复杂度θ(nlogn)

霍纳法则

计算二项式乘法结果：不断的把x从降次后的多项式中提取出来

问题化简

最小公倍数：求最大公约数

线性规划：背包问题

过河问题：简化为图

07 回溯法与分支限界法

DFS和BFS

DFS：栈，回边（未访问过的子-父）

BFS：队列，交叉边（子-访问过的父）

回溯法

回溯法是一个既带有系统性（深度优先策略）又带有跳跃性（先判断该子树是否包含问题的解，不包含就跳跃）的搜索算法，适用于解一些组合数较大的问题。

问题的解空间【动态生成】：对于问题的一个实例，解向量满足显式约束条件（对分量xi的取值限定）的所有多元组，构成了该实例的一个解空间。

解空间树：子集树（二叉树，如0-1背包）、排列树（排列，TSP）

解题步骤：

① 针对所给问题，定义问题的解空间； ② 确定易于搜索的解空间结构； ③ 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数（约束函数【不满足约束的点】+限界函数【得不到最优解的子树】）避免无效搜索。

好的约束函数能显著地减少所生成的结点数。但这样的约束函数往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷

子集树算法框架

排列数算法框架

排列生成问题

TSP问题

n皇后问题

0-1背包问题

分支限界法

分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树，裁剪那些不能得到最优解的子树以提高搜索效率。

步骤： ① 定义解空间(对解编码); ② 确定解空间的树结构； ③ 按BFS等方式搜索： a.每个活结点仅有一次机会变成扩展结点； b.由扩展结点生成一步可达的新结点； c.在新结点中，删除不可能导出最优解的结点；//限界策略 d.将剩余的新结点加入活动表(队列)中； e.从活动表中选择结点再扩展； //分支策略 f.直至活动表为空；

队列式FIFO分支限界

优先队列分支限界

0-1背包问题

装载问题

TSP问题

nl代表其当前所走路程的长度，Lb代表所有可行解的下界，即每一个节点的出边之和。 B(0，6)进队，其Lb=6的计算方式：找到邻接矩阵中每一行或者每一列除-1之外最小权值相加，即2+2+1+1=6。

回溯法与分支限界区别

回溯法与分支限界法

求解目标不同：一般而言，回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是尽快地找出满足约束条件的一个解；

搜索方法不同：回溯法使用深度优先方法搜索，而分支限界一般用宽度优先或最佳优先方法来搜索；

对扩展结点的扩展方式不同：分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点

存储空间的要求不同：分支限界法的存储空间比回溯法大得多，因此当内存容量有限时，回溯法成功的可能性更大。

回溯法与穷举法

穷举法：分解后检查。要将一个解的各个部分全部生成后，才检查是否满足条件，若不满足，则直接放弃该完整解，然后再尝试另一个可能的完整解，它并没有沿着一个可能的完整解的各个部分逐步回退生成解的过程。

回溯法：动态生成解空间。一个解的各个部分是逐步生成的，当发现当前生成的某部分不满足约束条件时，就放弃该步所做的工作，退到上一步进行新的尝试，而不是放弃整个解重来

08 动态规划

最优化原理(Principle of Optimality)：把多阶段过程转化为一系列单阶段问题,逐个求解，创立了解决这类过程优化问题的新方法一动态规划。 多阶段决策问题(MDP)：求解的问题可以划分为一系列相互联系的阶段，在每个阶段都需要作出决策，且一个阶段决策的选择会影响下一个阶段的决策。