探底排序的时间复杂度

很久很久之前看到过这么一个问题：炉石里一套牌共有 30 张，问至少要探底多少次才能保证可以将牌库排序成想要的顺序？这里给不了解背景的朋友介绍一下，所谓 探底，就是选择牌库底三张牌中的一张将其至于牌库顶。

我们来抽象一下这个题：对于一个大小为 \(n\) 的排列 \(P\)，一次操作可以把前三个数中的一个塞到最后。既然这是个排序算法，我们不妨将其称作 探底排序 好了…… 那么现在问题就是问探底排序的最坏情况下需要多少次操作。我们先研究一个简化版，每次只能把前两个元素中的一个塞到最后。

作为一名 TCS 大师，我对这个问题挺有兴趣的。但是显然，求出精确解看起来非常难（而且我怀疑甚至不存在通项），于是就退而求其次，分析一下其时间复杂度好了。

我们先来给出一个 \(O(n^2)\) 的算法，顺便证明其一定有解。idea 非常简单，我们就模仿选择排序，每次选出剩下的数中最小的一个。具体说来，算法分为 \(n\) 轮。第 \(k\) 轮过后，我们保证整个序列最后面 \(k\) 个元素一定依次是 1 到 \(k\)，这样 \(n\) 轮之后整个数组就有序了。在第 \(k\) 轮中，前 \(n - k\) 次，我们比较排列前两个数，并且将较大的那个数塞到最后去，这样 \(n - k\) 次之后，序列中第一个数一定是 \(k\)，且接下来 \(k - 1\) 个数依次为 \(1, \dots, k - 1\)，于是我们再把这 \(k - 1\) 个数塞到最后，最后把 \(k\) 塞到最后即可。伪代码如下：

for k from 1 to n:
    for _ from 1 to n - k: # 选 P[1] ... P[n - k + 1] 中最小的数
        if P[1] > P[2]:
            rotate(1)
        else:
            rotate(2)

    for _ from 1 to k - 1: # 此时 P[1] 一定是 k，将接下来的 1..k-1 塞到最后
        rotate(2)

    rotate(1) # 把 k 塞到最后去

复杂度分析就很简单了，显然是 \(O(n^2)\)，更确切一点，是刚好 \(n^2\)。

既然 upper bound 有了，我们再来整一个 lower bound 吧。直觉上应该也是 \(\Omega(n^2)\)，而且感觉把整个序列倒过来就需要这么多。不妨让我们来打个表试试：

n = 1, worst = 0, reverse = 0
n = 2, worst = 1, reverse = 1
n = 3, worst = 2, reverse = 2
n = 4, worst = 5, reverse = 4
n = 5, worst = 8, reverse = 6
n = 6, worst = 12, reverse = 11
n = 7, worst = 17, reverse = 14
n = 8, worst = 23, reverse = 22
n = 9, worst = 30, reverse = 26
n = 10, worst = 38, reverse = 37

我直接去 OEIS 上搜了一下 worst 这个序列，没找到，但是看着像是一个 \(\Omega(n^2)\) 的序列，而且我猜测奇数项和偶数项各自组成一个二次多项式。而且 \(n\) 为偶数的情况下，序列翻转几乎就是最坏情况了。接下来我们证明其 lower bound 为 \(\Omega(n^2)\)。

我们首先给出一个核心观察：

对于任何一个长度为 \(k < n\) 的操作序列 \(X\)，\(P\) 的前 \(k\) 个数对应的集合和 \(PX\) 的后 \(k\) 个数对应的集合至多只有一个数不同。

这个观察很好理解： \(PX\) 的后 \(k\) 个元素只能全部来自于 \(P\) 的前 \(k+1\) 个元素。这个观察带来的一个推论是，进行恰好 \(n\) 次操作后，\(PX\) 的前 \(\frac{n}{2}\) 个数和 \(P\) 的前 \(\frac{n}{2}\) 个数至多只有两个数不同（集合意义上）。

有了这个推论，我们就可以开始证明 lower bound 了。对于排列 \(P\)，假设 \(m\) 为最优操作的次数，\(X^*\) 为最优操作序列。我们把 \(X^*\) 分成若干段，第一段为 \(X'\)，长度为 \(m \bmod n\)，之后每段长度为 \(n\)。由于后面 \(m - (m \bmod n)\) 次操作将 \(P X'\) 进行排序，我们马上可以得到一个 lower bound： \[ m - (m \bmod n) \geq \frac{n}{2} d(P X'), \] 其中 \(d(Q) = |\{i: i \leq \frac{n}{2}, Q_i > \frac{n}{2} \}|\) 表示序列 \(Q\) 前一半中有多少个元素排序后不在前一半了。接下来，我们证明存在一个 \(P\) ，使得对于任何序列长度不超过 \(n\) 的 \(X'\) ，都有 \(d(P X') = \Omega(n)\)，这样就能够整出一个 \(\Omega(n^2)\) 的 lower bound。

令 \(n = 4k\)，我们把 \([n]\) 均匀分成 4 块 \([n] = (A, B, C, D)\)，其中 \(A = (1, \dots, k)\)，\(B = (k + 1, \dots, 2k)\)，\(C = (2k + 1, \dots, 3k)\)，\(D = (3k + 1, \dots, 4k)\)，并令 \(P = (A, C, B, D)\) 为一个 \([n]\) 的排列。为了得到了 \(d(P X')\) 的一个 lower bound，我们对 \(|X'|\) 分类：

• 如果 \(|X'| \leq k\)，那么 \(PX'\) 前一半中至少有 \(k - 1\) 个 \(C\)，故 \(d(P X') \geq k - 1\)；
• 如果 \(k < | X'| \leq 2k\)，那么 \(PX'\) 后一半中至少有 \(k - 1\) 个 \(A\)，故 \(d(P X') \geq k - 1\)；
• 如果 \(2k < |X'| \leq 3k\)，那么 \(PX'\) 前一半中至少有 \(k - 1\) 个 \(D\)，故 \(d(P X') \geq k - 1\)；
• 如果 \(3k < |X'| < 4k\)，那么 \(PX'\) 后一半中至少有 \(k - 1\) 个 \(B\)，故 \(d(P X') \geq k - 1\)。

这样，我们就代入之前的结果可得： \[ m \geq \frac{n}{2} d (P X') = \frac{n^2}{8} - O(n) = \Omega(n^2). \]

到这里，我们就得到了一个 tight 的 bound，\(\Theta(n^2)\)。但是还差那么一点点：打表给出的 \(n^2\) 的系数为 \(\frac{1}{2}\)，lower bound 给出的系数是 \(\frac{1}{8}\)，但是算法给出的 \(n^2\) 的系数为 1。我们能否把上下界的常数都改进到 \(\frac{1}{2}\) 呢？