时间复杂度
平均时间复杂度：典型情况性能$\Theta$
最坏时间复杂度：最坏情况性能$O$
分治
Merge Sort
MinMax Problem
二分答案+验证可行性，题目中一般有关键信息：某个值Val越大越容易使某种情况成立，求某种情况成立的最小的Val
Closeset Pair Problem
给定一个平面，有n个已知坐标的点，求最近的点对。
朴素想法1：根据x坐标进行二分，有了朴素想法1之后看到难点：怎么在n的复杂度内考虑完跨越边界的点
朴素想法2：根据两边已经产生的答案来进行一个限制，x和y同时限制之后，对于每个点只需要枚举不超过7个点
Convex Hull Problem
平面上有n个已知坐标的点，求他们的凸包
根据x坐标进行二分，合并的时候找上边的共线（斜率一样）和下边的共线，然后进行合并
DP
LCS
Knapsack
01背包
1个背包，给定容量，放价值最大的东西
$dp[i][j]$表示前$i$个物品一共消耗了$j$容量的最大价值，只需要考虑第$i$个物品取或者不取
进一步优化（背包问题的核心思想）：每一个物品只能取一次
用$dp[i]$表示消耗容量$i$的情况下获取的最大价值，仍然遍历物品，但是在转移时，直接从$C_{max}$转移到$C_{min}$，不会出现取多次的情况
完全背包
每个物品变为无数个，01背包转移的时候枚举数量。
双背包
背包变为2个，转移的时候将容量扩展一维，都从大到小遍历即可。
多重背包
每种物品有$s_i$种
朴素想法：直接转化为01背包来做
优化：做一个把每一个$s_i$转化成二进制的形式，二进制的每一位变成一种。
搜索
搜索
深度优先
广度优先
迭代加深
逐渐增加允许搜索的深度，找到最浅完备解，防止死循环
一致代价搜索
优先扩展当前路径代价最小的点（很容易联想到Dijkstra）
启发式搜索
启发函数h(n)要保证估计成本不能高于实际成本
贪心最佳优先搜索
考虑一个函数h(n)来评估预计n到目的点的距离，每次走n最小的
不保证最优解，而且有可能绕路
A*算法
考虑一个函数$f(n)=g(n)+h(n)$来评估，$g(n)$表示当前已经花费的探索成本，由此来取得一个平衡
能够保证最优解，但是空间复杂度非常吓人
Online Algorithms
ALG/OPT
ALG表示在线算法的性能
OPT表示离线算法的性能
竞争比（Competitive Ratio）
竞争比是衡量在线算法性能的重要指标，用于比较在线算法与最优离线算法的结果。
定义
对于一个在线算法 $\text{ALG}$，其竞争比定义为：
$CR = \sup_I \frac{\text{ALG}(I)}{\text{OPT}(I)} \quad \text{(对于收益最大化问题)}$
其中：$CR \geq 1$，竞争比越接近 1，在线算法的性能越接近最优离线算法。
- 问题描述：
- 每天可以选择租滑雪板（每天花费$ 10）或直接购买滑雪板（一次性花费 $100）。
- 问题是你不知道总共需要滑雪多少天。
- 分析：
- ALG：在线算法的策略，租到第 10 天时购买。
- OPT：最优离线算法的策略，知道总天数 n，如果 $n \geq 10$，直接购买，否则每天租用。
在线缓存问题（Caching Problem）
- 问题描述
- 有一个容量为 k 的缓存，用于存储最近访问的 k 个数据。
- 数据访问请求是按序列到达的，如果请求的数据不在缓存中（缓存未命中），需要替换一个缓存数据。
- 分析
- ALG：在线算法的缓存替换策略， LRU（最近最少使用） 或 FIFO（先进先出）。
- OPT：离线算法知道所有未来请求序列，能够选择最优替换策略（通常是 Belady 算法）。
- 竞争比
- 在线缓存替换算法的竞争比一般为CR = O(k)。
NP-Completeness
P和NP
P是可以在多项式时间复杂度内由确定性算法解决的问题
NP是可以在多项式时间复杂度内验证解正确性的问题
NP-Complete问题
属于NP，而且是NP中最难得问题
如果某个NP完全问题能够在多项式时间内解决，则所有NP问题都可以在多项式时间内解决
NP-Hard
至少与NP完全问题一样难，但是不一定是NP类问题
常见NP完全问题
SAT和3-SAT：布尔公式赋值
旅行商问题：带权图中寻找经过所有城市一次且仅一次的最小总权重
定点覆盖问题：判断是否存在一个大小为k的定点集合，使得每一条边都至少一个端点在S中
哈密顿回路问题：无向图中判断是否存在一条回路，经过每个顶点一次且仅一次，最终回到起点
子集和问题：判断是否存在一个子集，子集中的元素和等于一个给定值