《算法设计与分析》复习

复习参考：
《算法设计与分析基础》潘彦译
【北大公开课】 算法设计与分析
【算法设计与分析】期末考试知识总结（知识超浓缩版）
《算法分析与设计》复习笔记
【期末知识点整理】算法设计与分析
算法设计与分析——算法复杂性分析

一、基础知识

• 算法是一系列解决问题的明确指令。换言之，对于符合一定规范的输入，能够在有效时间内获得要求的输出。

• 算法：具有输入、输出、确定性、有限性。

• 程序（算法+数据结构=程序）：具有输入、输出、确定性（注意：程序可以不满足有限性，如操作系统是在无限循环中执行的程序）。

• 衡量算法好坏的方法：正确性（有限时间正确结果）、简明性、效率（时间、空间）、最优性

• 算法的基本特征

  • 有限性：一个算法必须总是（对任何合法的输入值）在执行有限步之后结束
  • 确定性：算法中的每一条指令必须有确切的含义，不产生二义性
  • 可行性：算法中的每一条运算都必须是足够基本的，原则上能够精确的执行
  • 输入性：一个算法有零个或多个输入
  • 输出性：一个算法有一个或多个输出

• 背包问题

  • 蛮力法
    优点：简单明了
    缺点：时间复杂度高，对于大规模问题不适用。
  • 回溯法
    优点：时间复杂度较低，可以找到最优解
    缺点：需要额外的空间来存储递归过程中的解。
  • 动态规划
    优点：时间复杂度较低，可以处理大规模问题
    缺点：需要额外的空间来存储子问题的解
  • 贪心法
    该问题不具备贪心选择性质，通过局部最优，无法达到全局最优，故不能得到正确的解

二、算法效率分析基础

• 渐进意义下的符号：

  • Ο，表示渐进上界(tightness unknown)，小于等于的意思，近似复杂度。

  • Ω，表示渐进下界(tightness unknown)，大于等于的意思，近似复杂度。

  • Θ，表示确界，既是上界也是下界(tight)，就是相等，准确的复杂度。
    

• 常见的时间复杂度大小关系：O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) < O(nⁿ)
  

• 分析非递归算法效率的通用方案

  • 决定用哪个（哪些）参数表示输入规模
  • 找出算法的基本操作（作为一个规律，它总是位于算法的最内层循环中）
  • 检查基本操作的执行次数是否只依赖于输入规模。若它还依赖于一些其他的特性，则最差效率、平均效率以及最优效率（如有必要）需要分别研究
  • 建立一个算法基本操作执行次数的求和表达式
    （分析非递归的基本操作次数时，某些情况下需要建立一个递推关系，而不是一个求和表达式；在分析递归时递推关系更为常见）
  • 利用求和运算的标准公式和法则来建立一个操作次数的闭合公式，或者至少确定它的增长次数。
    

• 分析递归算法时间效率的通用方案

  • 决定用哪个（哪些）参数作为输入规模的度量标准
  • 找出算法的基本操作
  • 检查一下，对于相同规模的不同输入，基本操作的执行次数是否可能不同。若有该可能，则必须对最差效率、平均效率以及最优效率做单独研究。
  • 对于算法基本操作的执行次数，建立一个递推关系以及相应的初始条件。
  • 解这个递推式，或者至少确定它的解的增长次数

主定理法

对于递归式T(n) = aT(n/b) + f(n)，比较根节点代价之和f(n)和叶子节点代价之和的大小

也就是在比较合并成本和叶子成本，究竟谁更大。粗略的理解如下：
① f(n)多项式意义大于 ，不止渐进大于且相差n^ε，所以总体代价以f(n)为主；（这里忽略了对正则条件的理解，感觉不影响使用，想了解深层原理可以看一下课本）
② f(n)与 等阶，最后的结果要再乘以logn
③ f(n)多项式意义小于，不止渐进小于且相差n^ε，所以总体代价为
这三种情况画在线段上如下图所示，所以中间哪些无法覆盖的部分就是这个定理无法涵盖的情况。具体的讲解还是可以看看那个北航老师的视频。


注意：要使用第三种情况，需要满足条件验证，其中c<1

• 函数的阶具有传递性

三、蛮力法

【概述】蛮力法是一种简单、暴力、直接解决问题的方法，通常直接基于问题的描述和所涉及的概念定义，依赖计算机的计算速度直接求解。
【步骤】搜索所有的解空间、搜索所有的路径、直接计算、模拟和仿真。
【理解】有的暴力枚举即可，有的直接模拟即可。

字符串匹配

时间复杂度为O(nm)，其中n是主字符串的长度，m是模式字符串的长度
空复O（1）

最近对问题

暴力法 时复Θ（n²）
最近对问题的一个最重要的应用是统计学中的聚类分析。（填空）

凸包问题

• 对于平面上的一个点的有限集合，如果以集合中任意两点P和Q为端点的线段上的点都属于该集合，则称该集合是凸集合
• 凸包
  （直观版）对于平面上n个点的集合，它的凸包就是包含所有这些点（在内部或边界上）的最小凸多边形
  （正式版）一个点集合S的凸包是包含S的最小凸集合（最小即S的凸包一定是所有 包含S的凸集合 的子集）
• 凸包问题
  是为一个有n个点的集合构造凸包的问题。为了解决该问题，需要找出极点（作为这个集合的凸多边形的顶点）（填空）
• 解决方法：
  • 暴力法 时复O（n³）

穷举查找

旅行商问题

找出一条n个给定城市间的最短路径，其中要求回到出发的城市&每个城市都只访问一次。则该问题可以理解为求一个图的最短哈密顿回路问题。

哈密顿图（哈密尔顿图）（英语：Hamiltonian graph，或Traceable graph）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径（Hamiltonian path）

• 蛮力法求解哈密顿回路在最坏情况下需要考察所有顶点的排列对象，其时间复杂性为O(n!)

背包问题

时复 O(2ⁿ)

分配问题

有n个任务分配给n个人执行，一个任务对应一个人。给出对于每个任务，这n个人完成分别的成本。求总成本最小的分配方案。

• 蛮力法求解任务分配问题需要求解的排列数是n!

深度优先查找和广度优先查找

邻接矩阵O(n2)
邻接表O(n+e)
空间复杂度相同，都是O(n)

四、减治法

使问题变成与原问题相同的但是规模更小的子问题，解决这个子问题，延伸子问题的解决方法，从而得到原问题的解决方案

• 种类（期末可能考该题，填空）：
  • 减一个常量（如插排、拓排、全排列、求子集、dfs、bfs、堆排序）
  • 减一个常量因子（如二分查找、快速幂、俄罗斯乘法、约瑟夫斯、假币问题）
  • 减可变规模（如欧几里得算法、nim游戏、快排划分）

插入排序

减一

拓扑排序

删去入度为0的点

减常因子算法

折半查找

假币问题

在n枚外观相同的硬币中，有一枚是假币。在一架天平上，可以比较任意两组硬币，即通过观察天平是向右倾还是左倾或中间，课判断哪组更重。假设假币较轻。
进一步优化：增加堆数

俄式乘法

约瑟夫问题

减可变规模算法

计算中值和选择问题

插值查找

折半的优化
where：有序表

• 折半查找vs插值查找
  • 对于较小的文件，折半查找可能更好
  • 对于更大的文件和那些比较开销较大或访问成本较高的应用，插值查找更值得考虑

五、分治法

【概述】对于一个规模为n的问题，若该问题可以容易的解决（比如n的规模较小）则直接解决，否则将其分解为k个规模较小的子问题（即具有最优子结构性质），这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各子问题的解合并得到原问题的解。

• 分治法的设计思想是把一个难以直接解决的大问题分割为较小的子问题，分别解决子问题，最后把子问题的解组合起来形成原问题的解，这要求原问题和子问题的问题规模不同，问题性质相同（选择）
  【步骤】将大问题分解为若干个子问题、求解子问题、合并子问题的结果得到最终解。
  分治法的工作方案：
  （1）把一个问题划分为同一类型的若干子问题，子问题最好规模相同（平衡）
  （2）对这些子问题求解（一般使用递归），但问题规模 足够小时，也会利用另一个算法）(可独立求解)
  （3）有必要的的话，合并这些子问题的解，以得到原始问题的答案。
  【理解】分而治之，逐个击破。
• 分治法的使用条件
  （1）问题缩小到一定的规模（子问题）时易解决
  （2）原问题与分解后的子问题同类（即该问题具有最优子结构性质）
  （3）原问题的解可以由子问题的解合并得到
  （4）子问题相互独立，不包含公共问题。、

合并排序（归并排序）

优点：稳定性
缺点：需要线性的额外空间

快速排序

平均性能O(nlogn)

大整数乘法

四次变三次，减少乘法次数
=》通过代数变换，减少a（规约后的子问题个数）

Strassen矩阵乘法

用分治法解最近对问题和凸包问题

最近对问题

1、问题描述
求空间内，最近的两个点（最简单的就是一维问题，然后可以上升为二维的）
2、一维的最近点对的解题思路
同理，先分析是否满足分治法的适用条件：可以把空间分成两部分，求每个小空间的最近距离，但是在合并的时候，交界处比较难处理，但是也算是满足条件

• 分治法求解：
  • 分解：用各个点坐标的中位数m 作为分割点，分成两个点集
  • 解决：递归调用该算法，分别寻找两个点集上最接近的点对{p1, p2}、{q1, q2}及距离d1,d2
  • 合并：整个点集的最近点对或者是{p1, p2}，或者是 {q1,q2}，或者是某个{p3,q3}，其中p3和q3分属两个点集（整个情况在合并的时候要仔细分析）

合并策略：如果说两个点集的交界处有更近的点，那找到这俩个点，需要扫描的范围其实不会超过，两边的最近距离d的二倍，画个图如下所示，这2d的范围中，最多只可能会有4个点，如果说p1和p2之间还有其他的的点，那就会构成比d更近的距离了

所以，合并的时候，我们需要在从分割点 出发 分别往左右扫描扫描到d的距离，看看是否会出现更近的情况就可以啦

3、二维最近点对问题的解题思路
有了一维的基础，再考虑二维的问题就好理解多了，直接来分治法求解过程：
（1）预处理：将点集P中的点，按照X Y坐标从小到大顺序排列
（2）分解：计算x坐标中位数m，选择一条垂线L:x=m，将点集P分成左右两部分PL和PR，分解到最后的递归出口，剩1~3个点时，就可以直接计算了
（3）解决：递归调用该算法，分别找PL和PR中的最近点对及距离，距离分别记为δL, δR，置δ = min(δL, δR)
（4）合并：考察带状区域中的点
① 找出以L为中心线，宽度为2