学习目录
- 算法
-
- ①基本概念题(一切为了期末考试！)
- ②递归与递推
-
- --------------------------------------------------递归算法--------------------------------------------------
- --------------------------------------------------递推算法-----------------------------------------------------
- ③枚举法/蛮力法/穷举法/暴力法
- ④回溯算法/试探法
- ⑤分治算法
- ⑥贪婪算法
- ⑦动态规划（算法or思想）
算法
①基本概念题(一切为了期末考试！)
.
- 计算机求解问题的步骤：问题分析、数学模型建立、算法设计与选择、算法的表示分析实现、编制结果文档。
- 算法设计是解决问题的核心。
- 算法的定义：解决问题方法和步骤的描述是指令的有限序列。
- 算法三要素：控制结构、数据结构、操作。
- 算法的基本特征：有穷性、可行性、确定性、输入、输出
- 评价算法质量的指标：正确性、可读性、健壮性、高效率与低存储需求。
- 算法设计方法：结构化方法、面向对象方法
- 表示算法的方式：自然语言、盒图、流程图、PAD图、伪代码、计算机程序设计语言
- 评价算法的两个方面：人对算法维护的方便性、算法运行时占用机器资源得多少（时间效率与空间效率）。
- 评价算法的三个标准：算法实现所耗费时间、所耗费空间（主要考虑辅助变量）、算法应该易于理解易于编码易于调试。
- 可以在多项式时间内解决的判定性问题叫P类问题，在多项式时间内可以验证一个解是否正确的叫NP问题。
.
.
.
.
.
.
②递归与递推
--------------------------------------------------递归算法--------------------------------------------------
一、思想：自己调用自身函数的算法。
二、特点：
（1）在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
（2）在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等，所以一般不提倡用递归算法设计程序。
三、例题
（1）汉诺塔等
--------------------------------------------------递推算法-----------------------------------------------------
一、思想：即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。
二、特点
（1）相对于递归算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。
（2）顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。
（3）逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。
三、例题
（1）兔子生崽（斐波那契数列）
.-----------------------------------------------------------------------------------------------------------------------------------------------
.
.
.
.
.
③枚举法/蛮力法/穷举法/暴力法
一、算法思想：枚举所有可能的解。
二、特点（优劣）：
（1）过程简单且得到的结果一定正确。
（2）可能做了很多的无用功，浪费时间空间，效率低。
三、枚举算法解题的基本思路：
（1）确定枚举对象、范围和判定条件。
（2）逐一枚举可能的解并验证是否是问题的解。
四、枚举算法步骤：
（1）确定解题的可能范围，不能遗漏任何一个真正解，同时避免重复。
（2）判定是否是真正解的方法。
（3）为了提高解决问题的效率，使可能解的范围将至最小。
五、例题
（1）百钱买百鸡（偷懒不自己写了） java版代码
.
.
.
.
.
④回溯算法/试探法
一、算法思想：在问题的解空间树中，按深度优先策略DFS，从根节点出发搜索解空间树。算法搜索至解空间树的任一结点时，先判断该结点是否包含问题的解。如果不包含，则跳过对以该结点为根的子树的搜索，逐层向其祖先结点回溯。否则进入该子树，继续按深度优先策略搜索。
二、特点（优劣）：
（1）与深度优先算法不同的是搜索过程伴随着“剪枝操作”即当判断当前节点下无所需解时不再向下搜索，节省了空间提高了效率。
（2）剪枝函数：为了避免无效搜索，提高回溯法的搜索效率而存在的函数。通常可以用两种方式进行剪枝：
- 用约束函数在扩展结点处减去不满足约束条件的子树。
- 用限界函数减去得不到最优解的子树。
（3）回溯算法求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。
（4）是一种一遍搜索一边构造空间树的算法
（5）缺点是比较慢，递归求解，排列树思想要搜索出所有的解，类似于暴力求解，时间复杂度高。
//子集树 时间复杂度 O(2^n)
void backtrack(int t) {
if (t > n) {
Output(x);
} else {
for (int i = 0; i <= 1; i++) {
x[t] = i;
if (constraint(t) && bound(t)) { // 剪枝函数
backtrack(t + 1);
}
}
}
}
//排列树 时间复杂度O(n!)
void backtrack(int t) {
if (t > n) {
Output(x);
} else {
for (int i = t; i <= n; i++) {
swap(x[t], x[i]);
if (constraint(t) && bound(t)) { // 剪枝函数
backtrack(t + 1);
}
swap(x[t], x[i]);
}
}
}
三、回溯算法解决问题步骤：
（1）针对所给问题，定义问题的解空间（子集树，排列树）。
（2）确定易于搜索的解空间结构。
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
四、例题
（1）组合问题看看其他大佬的代码吧哈哈
（2）皇后问题背包问题
.
.
.
.
.
⑤分治算法
一、算法思想：分而治之，把一个复杂的问题分成多个相同或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单地直接求解，原问题的解即子问题的解的合并。
二、特点（优劣）：
（1）往往伴随着递归的使用：分治与递归经常同时应用在算法设计中。
（2）可能做了很多的无用功，浪费时间空间，效率低。
（3）最优子结构性质：如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。
（4）自底向上，各个子问题独立
三、分治算法步骤：
（1）分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
（2）解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
（3）合并：将各个子问题的解合并为原问题的解
四、例题
（1）排序算法(快速排序，归并排序)
（2）二分搜索
（3）棋盘覆盖
（4）最接近点对问题
（5）循环赛日程表
（6）汉诺塔
漫画版学习分治算法
.
.
.
.
.
⑥贪婪算法
一、算法思想：在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的
二、特点（优劣）：
（1）得到的结果是局部最优的，不一定是全局最优的，但结果都与最优解近似。
（2）每一步必须满足以下条件：
1、可行的：即它必须满足问题的约束。
2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择。
3、不可更改：即选择一旦做出，在算法的后面步骤就不可改变了。
（3）选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
三、贪婪算法步骤：
（1）将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
（2）证明做出贪心选择后，原问题总是存在最优解，即贪心算法总是安全的。
（3）证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。
四、例题
（1）钱币找零
（2）力扣分糖果
（3）背包问题
.
.
.
.
.
⑦动态规划（算法or思想）
一、算法思想：将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
二、特点（优劣）：
（1）最优子结构性质、重叠子结构、无后效性（“未来与过去无关”，这就是无后效性。）
（2）动态规划其实就是有条件约束的递推（更像是一种优化）。
三、动态规划步骤：
（1）描述优解的结构特征。
（2）递归地定义一个最优解的值。
（3）自底向上计算一个最优解的值。
（4）从已计算的信息中构造一个最优解。
四、例题
（1）01背包、子数组和
（2）其他讲解
————————————————————以上如有错误欢迎指正--------------------------------------------------------------
