原地算法系列

写完《O(n) 原地归并的稳定版本》后，我觉得我又行了，打算开坑原地算法系列。

已发布文章，新文章会在这里更新：

# 1. 原地算法的严谨定义

讨论学术算法时，原地的含义就是额外空间复杂度为 $O(1)$ ，那怎么定义额外空间复杂度呢？

我们从图灵机开始说起。

# 1.1. 图灵机模型

众所周知，图灵机由无限长纸带、读写头和状态寄存器组成，纸带上是离散的存储单元，存储有限字符集里的一个字符。

但是图灵机并不适合作为大多数算法的模型，它和现实机器差太远了。

第一，从时间角度。指定一个地址读取元素，又叫随机访存，图灵机需要 $O(n)$ 时间复杂度（把读写头移过去），黄花菜都凉了。

第二，从空间角度。由于字符集是有限的，存储纸带上的一个地址需要 $O(\log n)$ 个存储单元，这已经不满足“原地”的要求了。

# 1.2. RAM (Random Access Machine) 模型

为了解决图灵机的痛点，RAM 模型的做法很直接。RAM 引入了一个内存，允许常数时间完成随机访存。同时，每个存储单元可以存放任意整数。

RAM 的模型能力一下子就变得非常强大，而且强大过头了，以至于所有算法都可以改造成原地算法。这是因为我们可以轻松在 1 个存储单元里编码近乎无限的信息，把额外内存都编码进去，就实现了常数空间复杂度。

# 1.3. Word RAM 模型

在 RAM 基础上进行修正，就有了 Word RAM 模型。Word RAM 模型的存储单元是 Word，可容纳 w 比特，要求刚好能表示内存里每个存储单元的地址（没错在 C 语言里就是 size_t）。一个　Word 能存储指针，但是存不了更多的信息。

Word RAM 模型不仅足够强大，同时恰好解决了 RAM 模型的漏洞，因此它成为算法分析的事实标准。

这里不得不提 Word 压位“作弊”，借助位运算可以把 w 个 bool 压到一个 Word 里。这在原地算法领域是有争议的，反对者认为应该禁止位运算阻止这个操作。

# 2. 有没有工程意义

原地算法或许有工程意义，但我不关心工程。

很多原地算法带有巨大常数。为了让它具有工程意义，需要花很多代码、写很多边界来优化它，这与我的初衷相悖。我更关心算法的精妙，而不是反复尝试各种优化方案，一遍遍调性能。工作的性能优化已经做了很多了，业余时间还是少接触点吧。

# 3. 实战之原地选择算法

来都来了，再讲一个简单且广为人知的 BFPRT 算法，又叫 median of medians。它用于划分整个数组为前 k - 1 小的数、第 k 小的数、剩下的数，功能等价于 std::nth_element。

BFPRT 算法是快速选择 (quick select) 算法的改进，保证了最坏复杂度 $O(n)$ ，当然常数也会大很多。

# 3.1. 快速选择算法

快速选择是随机选一个元素作为 pivot，将数组进行三路划分，划分为小于 pivot、等于 pivot、大于 pivot 的三个区间。如果 k 落在了第 1 或 3 区间就递归。

这里的三路划分意图很明显，如果二路划分，中间是一个数来分割，元素都相同会导致复杂度退化成 $O(n^2)$ 。

快速选择在每次选最小 / 最大的数时，会退化到 $O(n^2)$ 。实际上随机选数已经很好地避免了最坏情况，因此工程上也会以快速选择算法为主体，BFPRT 作为兜底。

# 3.2. BFPRT 算法

BFPRT 算法改进了选 pivot 的过程。我们每 5 个数一组进行排序，取组内的中位数，然后把这些中位数再取中位数（递归 BFPRT 算法）作为 pivot。

证明一下复杂度。可以看到，一共有 n/5 个组，每个组的中位数都大于等于同一组的 3 个数。因此中位数的中位数大于等于 $n/5/2$ 个组乘以 3 也就是 $\frac{3}{10}n$ 个数。

算法时间函数 $T(n)$ ，获取中位数的中位数时间 $T(\frac{1}{5}n) + O(n)$ ，三路划分 $O(n)$ ，然后递归最坏情况是 $T(\frac{7}{10}n)$ ：

$T(n)\le T(\frac{1}{5}n) + T(\frac{7}{10}n) + O(n)$

接下来可以用归纳法，让 $T(0)\le b$ ，然后 $T(i)\le ai+b$ 对于 $0\le i<n$ 成立，证明 $T(n)\le an+b$ 成立。

总之因为 $\frac{1}{5}+\frac{7}{10}<1$ ，直觉上就大概能猜到 $O(n)$ 了。为什么要 5 个数一组的原因也就在这里，因为 3 个数一组 $\frac{1}{3}+\frac{2}{3}=1$ ，复杂度变为 $O(n\log n)$ 了。

template <typename T>
void inplace_select(T* first, T* mid, T* last) {
    assert_or_throw(first <= mid && mid < last);
    int64_t len = last - first;
    constexpr int64_t group_size = 5;
    if (len < group_size) {
        std::sort(first, last);
        return;
    }
    // 获取每组中位数的中位数
    for (int64_t i = 0; i + group_size <= len; i += group_size) {
        std::sort(first + i, first + i + group_size);
        std::swap(first[i / group_size], first[i + group_size / 2]);
    }
    inplace_select(first, first + len / group_size / 2, first + len / group_size);
    // 三路划分
    T pivot = first[len / group_size / 2];
    T* it1 = std::partition(first, last, [pivot](T el) { return el < pivot; });
    T* it2 = std::partition(it1, last, [pivot](T el) { return el == pivot; });
    // 递归
    if (mid < it1) {
        inplace_select(first, mid, it1);
    } else if (mid >= it2) {
        inplace_select(it2, mid, last);
    }
}

完整代码包含测试：https://gist.github.com/axiomofchoice-hjt/f56dea2f171cfabb474de9c271c8b6e8 (opens new window)

# 3.3. 递归栈

聪明的读者很快就发现，递归栈有 $O(\log n)$ 额外空间复杂度，这显然不算真正的原地。

怎么消除递归栈，这是这篇文章留下的问题，后续我可以介绍更进一步的算法（如果我看得懂论文的话）。

# 4. 原地算法：戴着镣铐跳舞

原地算法就像戴着镣铐跳舞，在最严格的空间限制下探索理论的边界。

就像《O(n) 原地归并的稳定版本》记载的，同时满足基于交换、稳定、原地、 $O(n)$ 时间复杂度的归并。看似不可能，但是看完了唯一值、分块、单双缓冲区的解法后，我不得不承认，算法的世界有太多未知。

我估计看的人不多，就当作自娱自乐了。

← O(n) 原地归并的稳定版本