下界问题

  • 什么是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$ 最小,则这是一个完全二叉树,所以我们有:

另一个例子是查找。由于查找有三种结果(<=>),所以这是个三叉树决策树,同样有:

上面决策时主要是看 $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$ 排序可归约为欧氏最小代价生成树