算法基础

分治法的基本思想： 将一个规模为 n 的问题分解为 k 各规模较小的子问题， 这些子问题互相独立且与原问题是同类型问题。 递归地解这些子问题， 然后把各个子问题的解合并得到原问题的解。

分治法所能解决的问题一般具有的几个特征是： 该问题规模缩小到一定程度就可以容易地解决； 该问题可以分解为若干个规模较小的同类型问题； 利用该问题分解出的子问题的解可以合并为该问题的解； 原问题分解出的各个子问题是相互独立的， 即子问题之间不包含公共的子问题。

分治法可以解决的具体问题：矩阵连乘、大数乘法、二分法搜索、快速排序、合并排序

合并排序的基本思想： 将待排序元素分成大小大致相同的 2 个子集合， 分别对 2 个子集合进行排序，然后将已排序的两个子集合合并成排好序的集合。 如果分割后的子集合还是比较大， 则继续分治， 直到分成的子集合只包含一个元素。 合并排序的时间复杂度是 O（nlogn） ， 是排序算法中的渐近最优算法。

快速排序的基本思想： 对于输入的数组， 以第 1 个元素为基准元素将数组划分成 3 段， 基准元素在中间， 小于等于基准元素的在前面， 大于等于基准元素的在后面； 对第 1 段和第 3 段驻足重复以上过程， 直到每一部分只有一个元素为止。 快速排序的平均时间复杂度是O（nlogn）。

分治法与动态规划法的异同： 相同点是， 将待求解的问题分解成若干个子问题， 先求解子问题， 然后从这些子问题的解得到原问题的解； 不同点是， 适合用动态规划法求解的问题， 经分解得到的子问题可以不相互独立， 而用分治法求解的问题， 经分解得到的子问题往往是相互独立的。设计动态规划算法的主要步骤： 证明最优子结构性质， 确定递归式， 计算最优值， 构造最优解。

动态规划算法的两个基本要素是（ 最优子结构性质） 和（ 重叠子问题性质）。

贪心算法的基本思想： 首先根据题意， 选取一种度量标准（ 即贪心策略）， 然后通过一系列的选择得到问题的解。 它所做出的每一个选择都是当前状态下局部最好选择。

单源最短路径Dijkstra算法、最小生成树算法prim和Kruskal算法都是贪心算法。

用回溯法解题的一个显著特征是搜索过程中动态产生问题的解空间。 在任何时刻， 算法只保存从根结点到当前扩展结点的路径。 如果解空间树中从根结点到叶结点的最长路径的长度为 h(n) ， 则回溯法所需的计算空间通常为 O（h(n)）。

回溯法的基本步骤：（ 1） 针对所给问题， 定义问题的解空间；（ 2） 确定易于搜索的解空间结构；（ 3）以深度优先方式搜索解空间， 并在搜索过程中用剪枝函数避免无效搜索。

分支限界法的基本思想： 分支限界法常以广度优先或最小耗费（ 最大效益） 优先的方式搜索问题的解空间树。 在分支限界法中， 每个活结点只有一个机会成为扩展结点。 活结点一旦成为扩展结点， 就一次性产生其所有子结点。 在这些子结点中， 导致不可行解或导致非最优解的子结点被舍弃， 其余子结点被加入活动结点表中。 此后， 从活结点表中取下一个结点成为当前扩展结点， 并重复上述过程， 直到找到所需解或活动结点列表为空为止。

分支限界法的搜索策略是： 在扩展结点处， 先生成它的所有子结点， 根据剪枝函数将满足条件的子结点加入活结点表中， 然后再从当前的活结点表中选择一个最有利的结点作为下一个扩展结点。

分支限界法与回溯法的异同： 相同点是， 都是一种在问题的解空间树种搜索解得算法； 不同点是， 求解目标不同（ 回溯可以找全部解可以找最优解， 分支限界找最优解）， 搜索方式不同（ 回溯深度优先， 分支限界广度优先或按优先级）， 对扩展结点的扩展方式不同（ 回溯一次一个子结点， 分支限界一次产生所有结点）， 对存储空间的要求不同（ 回溯用一个数组存放活结点， 分支限界用一个优先队列存放活结点）。

用确定性图灵机在多项式时间内可解的判定问题称为 P 类问题； 用非确定性图灵机在多项式时间内可解的问题称为 NP 类问题； 对于一个 NP 问题 X， 如果其他所有的 NP 问题都可以在多项式时间内归约为 X， 则 X 称为 NP 完全问题。