• 什么是P & NP问题？
• 求解个问题的算法复杂度下界
• 复杂度下界的分析方法
  • 输入输出分析法–平凡下界
  • 决策树法—紧(凑)下界(Tight bound)
    • 分析决策树的深度
    • 排序算法、查找、元素决策树的算法复杂度下界分析
  • 归约法—紧(凑)下界
    • 定义、记号
    • 凸包、最近点对、欧氏最小代价生成树问题的算法复杂度下界

一些概念

算法设计中主要有两类问题：

• 优化问题：求最……
• 判定问题：是否存在、是否满足……

优化问题与判断问题可以相互转换。比如：求字符串中出现最多的元素，这是优化问题。我们可以转换为是否存在出现 n 次的元素（n=1,2,……）。

---

• 确定性算法（Deterministic Algorithm）：算法的每个步骤只有一个选择。
• 非确定性算法（Non-deterministic algorithm）：先猜测问题的可能解，然后验证解的正确性
• P问题（Polynomial problem）：存在多项式时间的确定性算法的问题。
• NP问题（Non-deterministic polynomial probels）：存在多项式时间，但是非确定性算法的问题

判断问题的归约：在多项式时间内，可以将 $\Pi$ 问题的输入转化为 $\Pi’$ 问题的输入，并且两个问题的解一致，则称 $\Pi$ 可以归约到 $\Pi’$，记为 $\Pi \propto_\text{poly} \Pi’$

如果任一NP问题 $\Pi$都可以归约到NP问题 $\Pi’$，则 $\Pi’$ 称为 NP 完全问题

平凡下界

从问题的输入和输出规模确定的下界称为平凡下界。

比如我们要求 $n$ 个元素的排列，总共 $n!$ 个排列，那么这个算法的下界就是 $\Omega(n!)$

又比如要求 $f(x)=a_n x^n+\cdots+a_1x+a_0$，由于每个系数 $a_i$ 都会处理到，所以下界为 $O(n)$

如果未说明是下界，那么一定要用 $\Omega$；如果说明了是下界，那么 $O$ 也可以接受。只要不引起歧义即可。

平凡下界的局限性在于：平凡下界往往太低, 很多情况下用处不大；确定输入数据的哪一部分所有算法都必须处理到也很困难

如果真的存在一个算法能带到下界，这称这个下界是紧致的(Tight)

利用决策树来确定下界

顺着决策树往下走，每个结点都是一次决策，当走到叶子结点时说明得到了答案。所以从决策树的根到叶的最长路径的长度就是下界，即深度=下界。

比如在排序中，我们往往需要比较多个数，通过比较的结果得到相应的排序，这种叫排序决策树，从根到叶的一条路径表示对某种输入分布的比较踪迹，路径长度即为对该输入排序的比较次数。

对于 $n$ 个数的排序决策树，有 $n!$ 种排序方式，即 $n!$ 个叶结点，要让深度 $k$ 最小，则这是一个完全二叉树，所以我们有：

\[2^k \geq n!\\ \Rightarrow k \geq \log n! \geq \log (\frac{n}{2})^\frac{n}{2}\\ \geq \frac{n}{2} \log \sqrt{n} \geq \frac{n}{4} \log n\\ \Rightarrow O(n\log n)\]

另一个例子是查找。由于查找有三种结果（<=>），所以这是个三叉树决策树，同样有：

\[3^k \geq 2n+1\\ \Rightarrow k \log 3 \geq \log (2n+1)\\ \Rightarrow k \geq \frac{1}{|log 3}\log (2n+1)\\ \geq \frac{1}{\log 4}\log (2n+1) \geq \frac{1}{2} \log n\\ \Rightarrow O(\log n)\]

上面决策时主要是看 $f(x,y)=x-y$ 的大小，并按 $=0$、$<0$、$>0$ 分。如果将这个函数变成一个多项式 $f(x_1,x_2,\cdots,x_n)$，就得到 代数决策树；如果是线性代数（只有0、1次项），就得到 线性代数决策树。

归约

时间不够了，简单说一下一些问题的归约：

• 排序问题可归约到凸包问题
• $x_1,\cdots,x_n$ 元素唯一性问题可规约为最近点对问题
• $x_1,\cdots,x_n$ 排序可归约为欧氏最小代价生成树