次线性算法与有序判定问题

Posted on 2020-07-11 Edited on 2022-06-14 Views:

什么是次线性算法？

如何衡量算法的效率？一般来说，问题（以及对应的算法）可以分为以下几类：

不可判定问题。这种问题不存在算法。
指数时间可解。这种问题虽然存在算法但是就目前我们的技术水平，对于大输入，它们没办法在可接受的时间内返回结果。
多项式时间可解。这些算法可以在现在的电脑上较为高效地运行。
线性时间可解。这是大多数人认为的最高效算法，一般来说不会有比这更高效的了（读取输入就是线性的，不读完输入怎么计算输出？）
次线性时间算法。“次线性”(sublinear)即“线性以下”，指在利用低于与输入线性的资源（可以是时间也可以是空间）的情况下解决问题的一类算法。这类算法有着非常不可思议的特性：它甚至都不会看完完整的输入！

为什么我们需要次线性算法？

大数据时代我们要处理的数据是在是太多了，光是谷歌一天就会产生20PB的数据，我们根本没有足够的时空资源来哪怕运行线性的算法或者把它们全部过一遍！但是我们又希望从这些数据中挖掘有价值的结论，就只能求助于次线性算法了。

因为次线性算法没法看到完整的输入，给出错误的结果自然是情有可原的（在精确解没法在次线性时间内算出的情况下）。因此，次线性算法多是近似算法。同时，因为如果一个算法是确定性的，对手就可以预判这个算法会看那部分输入，并针对这个造出会让算法100%翻车的数据，因此随机化在次线性算法的设计也经常出现。

查询模型

好，既然次线性算法不能把输入完整地读一遍，那么要怎么样才能获取输入的信息呢？我们将次线性算法获取输入信息的方式称为查询（query）。而算法的难易自然和可以进行的查询方式有着很大的关系，因此我们还需要一组规则定义在一个问题中可以进行何种方式的查询，这种规则称一个问题的查询模型（query model）。例如，在以数组为输入的问题当中，常见的查询方式是按照一个下标询问对应的值，在以图为输入的问题当中，查询可以是按照两点查询边权……可以看到，查询模型是因问题而异的。

有序判定问题（Sortedness Problem）

定义

输入：一个个元素的数组。

查询模型：对于一个整数 $1\le i \le n$ ，查询 A_i 的值。

目标：在尽量少的时间内（假设一次查询时 $\mathcal{O}(1)$ 的）判断这个数组是否是有序（此处单指升序）的。

很显然，任何一个确定性的算法都必须进行 $\Omega(n)$ 次查询才能解决这个问题（不然肯定会有漏看的）。

因此我们退而求其次：如果运用随机化的话，我们能不能在 o(n) 次查询之内给出正确概率至少为 $\frac{1}{2}+\epsilon\ (\epsilon >0)$ 的答案呢？

（正确概率在这里只要大于 $\frac{1}{2}$ 就行，精确的值没有意义，因为我们总是可以重复运行不靠谱的算法提高正确率）

答案还是不行（证明课上似乎没讲？）

那我们怎么办？只好稍微把题目修改一下，再退而求其次看看能不能有高效的近似算法了。

修改后的定义

我们不妨寻找这么一个算法，它

在数组有序的时候输出是
在数组“非常无序”的时候输出否
而对于那种非常接近有序的数组，我们干脆不管。

设计这样的算法显然比设计能够精确解决这个问题的算法要容易多了。

那么怎么样算是“非常无序”，怎么样算是“接近有序”呢？显然，我们需要在数学上给予这些描述严谨的定义。

定义：对于 $\epsilon\in(0,1)$ ，如果需要至少修改 $\epsilon n$ 个数才能让数组变为有序，那么称数组是 $\epsilon$ 无序（ $\epsilon$ -far from sorted）的。

那么我们就可以进一步精炼我们上面的问题了：我们需要设计一个算法，使其

在有序的时候输出是
在 $\epsilon$ 无序的时候输出否

（ $\epsilon$ 是算法的一个参数）

从这里其实可以看到对于近似算法的一种设计思路：对于数值型的问题，我们通过对于最优解的放缩定义了近似比 $\alpha$ ，而对于判定型的问题，我们试图放宽需要判定的条件。在上面的问题当中我们相当于变相假设，或者说承诺了要么是有序要么是 $\epsilon$ 无序的，因此这种问题被称作promise problem。

二元数组

我们先从最简单的情形开始分析：如果数组只有和两种元素呢？

初步分析

显然此时数组有序等价于所有的都在前面。

我们不妨定义两个集合， L_1 和 R_0 。如果将数组里的元素从左到右排列， L_1 表示最靠左的 $\frac{\epsilon n}{2}$ 个的下标集合， R_0 表示最靠右的 $\frac{\epsilon n}{2}$ 个的下标集合。

显然在数组有序时， L_1 整体都在 R_0 右边。而当数组不有序时，有可能：

和的区间重叠。
在的左边。

接下来我们证明：

引理：如果是 $\epsilon$ 无序的，那么 L_1 必定在 R_0 左边且不重叠。

证明：我们使用反证法，不妨假设 L_1 和 R_0 有重叠的部分：

$0,0,\cdots,\rlap{\ensuremath{\overbrace{1,\cdots,1,0,1}^{L_1}}}1,\cdots,1,\underbrace{ {\color{blue}{0} },{\color{red}{1} },0,\cdots,0}_{R_0},\cdots1,1$

$\color{red}1$ 是 L_1 中最右边的， $\color{blue}0$ 是 R_0 中最左边的。

由 L_1,R_0 的定义可知， $\color{red}1$ 左侧的的数量严格小于 $\frac{\epsilon n}{2}$ ， $\color{blue}0$ 右侧的的数量也严格小于 $\frac{\epsilon n}{2}$ 。而注意到如果把 $\color{red}1$ 的左侧改成，把 $\color{blue}0$ 右侧的的改成，那么数组就变得有序了，而此时我们修改的元素数量严格小于 $\epsilon n$ ，这和数组是 $\epsilon$ 无序的前提是矛盾的。

算法

接下来我们给出能够以 $1-\delta$ 的成功率判定二元数组有序性的算法：

从数组当中随机选取 $t=\frac{2}{\epsilon}\ln\frac{2}{\delta}$ 个下标 $i_1,\cdots,i_t$ （为了简化分析，允许下标重复）。
查询 $A_{i_1},\cdots, A_{i_t}$ 的值。
如果在 $\left\{A_{i_1},\cdots, A_{i_t}\right\}$ 当中发现了逆序对，输出否，否则输出是。

分析

很显然，如果数组是有序的，那么我们的算法一定会输出是，成功率 $1>1-\delta$ 。

而如果数组是 $\epsilon$ -无序的，为了证明此时的成功率至少为 $1-\delta$ ，我们只需要证明

$\operatorname{Pr}[\text{wrong answer}] \le \delta$

即错误（输出了是）概率不大于 $\delta$ 。

设随机事件 E_L 表示在随机选取的个下标中，至少有一个下标来自 L_1 ， E_R 表示至少有一个下标来自 R_0 。

那么由之前的引理，如果 $E_L\cap E_R$ ，我们一定找得到逆序对。

因此只有可能在 $\overline{E_L\cap E_R}$ 才有可能出错：

$\begin{aligned} \operatorname{Pr}[\text{wrong answer}] \le \operatorname{Pr}\left[\overline{E_L}\cup\overline{E_R} \right] \le \operatorname{Pr}\left[\overline{E_L}\right] + \operatorname{Pr}\left[\overline{E_R}\right] \end{aligned}$

而

$\begin{aligned} \operatorname{Pr}\left[\overline{E_L}\right] &= \left(1-\frac{\left|L_1\right|}{n}\right) ^ t \\ &= \left(1-\frac{\epsilon}{2}\right)^{\frac{2}{\epsilon}\ln\frac{2}{\delta}} \\ &\le \left(e^{-\frac{\epsilon}{2}}\right)^{\frac{2}{\epsilon}\ln\frac{2}{\delta}} \\ &= \frac{\delta}{2} \end{aligned}$

倒数第二步我们运用了不等式 $1+x\le e^x$ 。

同理可证 $\operatorname{Pr}\left[\overline{E_R}\right] \le \frac{\delta}{2}$ ，因此

$\operatorname{Pr}[\text{wrong answer}] \le \operatorname{Pr}\left[\overline{E_L}\right] + \operatorname{Pr}\left[\overline{E_R}\right] \le \frac{\delta}{2} + \frac{\delta}{2} = \delta$

证毕。

时间复杂度

随机采样花费的时间复杂度为 $\mathcal{O}(t)$ 。

查询子数组花费的时间复杂度也是 $\mathcal{O}(t)$ 。

而在子数组当中查找逆序对也可以被优化成 $\mathcal{O}(t)$ ，实现的方法有很多，例如可以计算的下标的最小值和的下标的最大值进行比较等。

因此这个算法的时间复杂度就是 $\mathcal O(t) = \mathcal O\left(\frac{1}{\epsilon}\ln\frac{1}{\delta}\right)$ ，和无关。

一般情况

接下来我们来看数组元素可以是任意数字的情况。

我们之前随机采样的想法还能继续沿用吗？

考虑如下情况：

$3,2,1{\color{red}|}6,5,4{\color{red}|}9,8,7$

虽然这个数组是 $\frac{2}{3}$ 无序的，但是如果我的随机采样在每个段中只挑了一个元素，那采样出来的子序列却一定是有序的，我们的算法就被糊弄过去了。

这就是问题所在：如果我们把一个数组分成若干段“总体有序，但局部无序”的连续段，显然这样的段最多可以有 $\mathcal O(n)$ 个。而为了能够在子序列当中找到逆序对，就必须从同一个段当中至少选两个数。而由生日悖论可知，为了大概率确保能从一个段中选两个数，我们必须至少随机选 $\mathcal O\left(\sqrt n\right)$ 个数——这让我们之前的分析几乎废掉。

那怎么办呢？

考虑一个有序的数组所具有的性质。在算法层面，一个熟悉的性质便是：可以进行二分查找。

这给我们一个思路：如果我们不管三七二十一在给定的数组上跑二分，如果二分翻车了，那么数组一定是无序的，如果二分没翻车，数组或许就是有序的。

如何定义二分有没有“翻车”？或者说，如何定义一次正常的二分？

引入一致二分查找（Consistent Binary Search）的概念，如果对于一次二分查找，

我最后找到了我要找的那个数（也就是说，如果我要找的是，而我的二分最后终止于下标），
假设二分的左右端点和终点分别为，二分的过程中始终成立，

那么我们称这次二分查找是“一致的”或“相容的”（我觉得翻译成哪个似乎都不大合适）。

算法

在二分思想的指引下我们提出如下的算法：

随机选择一个下标并查询的值。
二分查找。
如果这次二分查找是一致的，那么输出是，反之输出否。

分析

引理：如果对于 A_i 和 A_j 的二分查找都是一致的，而且 i<j ，一定有 A_i<A_j 。

证明：虽然两次二分查找中前几层的搜索区间可能相同，但由于 i < j ，到了某一层一定会出现 A_i 往左边， A_j 往右边的分歧。假设该层搜索区间的中点是 A_m ，显然对 A_i 的二分搜索之所以在这层之后往左走是因为 A_i < A_m ，同理可知 A_j>A_m ，将二式组合引理便得证。

假设表示所有对下标对应的数进行的二分搜索是一致的下标的集合。则由刚刚的引理，由中下标组成的原数组的子序列一定是有序的。因为原数组是 $\epsilon$ 无序的，因此必然有 $|C|<(1-\epsilon) n$ （可以通过反证法证明）。

这个结论有什么意义呢？要知道我们的算法在原数组有序的时候一定输出正确的结果，而在原数组无序时，我们算法只有在抽到中的下标时才会做出误判。因此我们算法的错误率的上界为 $1-\epsilon$ 。

在得出这个上界之后，我们就可以改进我们的算法了：

将之前的算法运行 $k=\frac{1}{\epsilon}\ln\frac{1}{\delta}$ 遍。
如果次运行的结果都为是，则输出是，反之则输出否。

这样的错误率是多少呢？

$\begin{aligned} \operatorname{Pr}[\text{wrong answer}] &\le \left(1-\epsilon\right)^k \\ &= \left(1-\epsilon\right)^{\frac{1}{\epsilon}\ln\frac{1}{\delta}} \\ &\le \left(e^{-\epsilon}\right)^{\frac{1}{\epsilon}\ln\frac{1}{\delta}} \\ & = \delta \end{aligned}$

因此正确率至少为 $1-\delta$ ，符合我们的要求。而这个算法的时间复杂度是 $\mathcal O\left(\frac{1}{\epsilon}\ln\frac{1}{\delta}\log n\right)$ ，也是相当优秀的。