数据结构期末复习

时间复杂度

平均时间复杂度：典型情况性能$\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中

哈密顿回路问题：无向图中判断是否存在一条回路，经过每个顶点一次且仅一次，最终回到起点

子集和问题：判断是否存在一个子集，子集中的元素和等于一个给定值