一、算法的基本概念
算法是求解问题的一系列计算步骤，用来将输入数据转换为输出结果。
1.算法的基本特征
有限性
确定性
可行性
输入性
输出性
2.算法设计需要满足的目标
正确性
可使用性
可读性
健壮性
高效率和低存储需求
3.算法和程序的区别
一、形式不同
1、算法：算法在描述上一般使用半形式化的语言。
2、程序：程序是用形式化的计算机语言描述的。
二、性质不同
1、算法：算法是解决问题的步骤。
2、程序：程序是算法的代码实现。
三、特点不同
1、算法：算法要依靠程序来完成功能。
2、程序：程序需要算法作为灵魂。
二、时间复杂度计算
1.大O表示法
"大O表示法"表示程序的执行时间或占用空间随数据规模的增长趋势。大O表示法就是将代码的所有步骤转换为关于数据规模n的公式项，然后排除不会对问题的整体复杂度产生较大影响的低阶系数项和常数项。
只关注循环执行次数最多的那段代码
加法法则（总复杂度等于量级最大的那段代码的复杂度）
乘法法则（嵌套代码复杂度等于内外代码复杂度的乘积）
2.最坏和平均情况
指算法在所有输入I下的所执行基本语句的最多执行次数和平均次数
3.根据递归方程求解时间复杂度
3.1 根据递归树求解
①画递归图
②相加化简得时间复杂度
3.2 根据主方法求解
主定理：a ≥ 1 和 b > 1，是常数，f ( n )是一个函数，T(n)是定义在非负整数上的递归式:
T(n) = aT(n/b) + f(n)，
若对某个常数 ε>0 有 f ( n ) = O ( n l o g b a − ε ) f(n) = O(nlog_ba-ε)f(n)=O(nlog
b
a−ε)，则 T ( n ) = Θ ( n l o g b a ) T(n) = Θ(nlog_ba)T(n)=Θ(nlog
b
a) 。
若f ( n ) = Θ ( n l o g b a ) f(n) = Θ(nlog_ba)f(n)=Θ(nlog
b
a)，则 T ( n ) = Θ ( n l o g b a ∗ l g n ) T(n) = Θ(nlog_ba*lgn)T(n)=Θ(nlog
b
a∗lgn)。
若对某个常数 ε>0 有 f ( n ) = Ω ( n l o g b a + ε ) f(n) = Ω(nlog_ba+ε)f(n)=Ω(nlog
b
a+ε)，且对某个常数 c<1 和所有足够大的 n 有 a f ( n / b ) ≤ c f ( n ) af(n/b) ≤ cf(n)af(n/b)≤cf(n)，则 T ( n ) = Θ ( f ( n ) ) T(n) = Θ(f(n))T(n)=Θ(f(n)) 。
三、六大算法
计算机解决问题其实没有任何奇技淫巧，它唯一的解决办法就是穷举，穷举所有可能性。算法设计无非就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。
------《labuladong的算法小抄》
1.分治法
1.1 算法思路
先「分」后「治」，先按照运算符将原问题拆解成多个子问题，然后通过子问题的结果来合成原问题的结果。
1.2 适用范围
该问题的规模缩小到一定的程度就可以容易地解决
该问题可以分解成若干个规模较小的相似问题
利用该问题分解出的子问题可以合并为该问题的解
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题
1.3 基本步骤
①分解出若干个子问题
②求解子问题
③子问题合并
2.回溯法（DFS）
2.1 算法思路
解决一个回溯问题，实际上就是一个决策树的遍历过程。（其实就是穷举，如果配合着剪枝技巧就是聪明的穷举）
注：DFS使用的数据结构是栈，往往利用递归来解决（递归调用利用的就是系统栈）
2.2 算法步骤
①针对给定的问题确定解空间
②确定结点的拓展搜索规则
③以深度优先搜索（DFS）的方式搜索解空间树，并在搜索过程中可以采用剪枝函数来避免无效搜索。
2.3 算法框架
result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择
2.4 算法技巧
①剪枝函数——聪明的穷举
对于一些明显不符合题意的分支进行剪枝，避免无效穷举。
②数组交换
这个用于解空间为全排列树的情况，而且保存路径的方式为数组，此时可以对数组数据进行交换来保证排列中的每个元素不同。
3.分枝限界法（BFS）
虽然不喜欢官方的定义，但是为了更好理解这个名字，还是要了解以下概念：
分枝——使用广度优先的策略
限界——使用限界函数计算函数值（可以理解为权重）来决定遍历顺序
3.1 算法思路
和回溯法一样都是穷举决策树，不过分支限界法使用**广度优先遍历（BFS） **的方式穷举。
这种穷举方式使分支限界法有以下特点：
①BFS 找到的路径一定是最短的，但代价就是空间复杂度可能比 DFS 大很多
②适用于找到某种意义下的最优解（其实也可以选择遍历决策树找到找到符合条件的解，但是这样一来时间复杂度和DFS一样，但是空间复杂度却高了很多，得不偿失）
③在找最优解中，BFS往往时间复杂度更低，但空间复杂度更高（不需要像DFS那样遍历所有节点，但代价就是需要额外空间来存储至少一层的结点）
④往往用队列/优先队列的数据结构
3.2 算法框架
// 计算从起点 start 到终点 target 的最近距离 int BFS(Node start, Node target) { Queue<Node> q; // 核心数据结构 Set<Node> visited; // 避免走回头路 q.offer(start); // 将起点加入队列 visited.add(start); int step = 0; // 记录扩散的步数 while (q not empty) { int sz = q.size(); /* 将当前队列中的所有节点向四周扩散 */ for (int i = 0; i < sz; i++) { Node cur = q.poll(); /* 划重点：这里判断是否到达终点 */ if (cur is target) return step; /* 将 cur 的相邻节点加入队列 */ for (Node x : cur.adj()) { if (x not in visited) { q.offer(x); visited.add(x); } } } /* 划重点：更新步数在这里 */ step++; } }
3.3 算法技巧
①优先队列
优先弹出更优的结点，这样可以更快找到最优解。
②双向 BFS 优化
传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。
在算法实现上还有技巧，每次扩散结点时选择较小一端（较小的队列），如果我们每次都选择一个较小的集合进行扩散，那么占用的空间增长速度就会慢一些，效率就会高一些。
不过，双向 BFS 也有局限，因为你必须知道终点在哪里。
