冒泡排序平均需要跑多少趟：拉马努金Q函数初探

摘要: 拉马努金Q函数在算法分析中的应用，初步体验

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，本文我们继续来讨论算法分析中的问题。

很多数组上的算法都与 $1 \sim n$ 的排列有关，比如各种排序算法。在分析数组上的排序算法时，排列上的各种概念对分析问题很有用，比如逆序、圈、左向右最大值、上升、下降、游程、峰、谷等等。

本文我们看一下逆序的概念及其在冒泡排序的分析中的作用。然后我们解决一个相关的算法分析问题：对于 $1 \sim N$ 的随机排列，$N \rightarrow\infty$ 时，冒泡排序平均要跑多少趟。

首先给出结论，$N \rightarrow\infty$ 时，冒泡排序平均扫描趟数为 $N - \sqrt{\frac{\pi N}{2}} + O(1)$。

为了推导以上结论，我们首先介绍一下排列中关于逆序、逆序数、逆序表的概念。然后介绍一下冒泡排序算法的流程，然后根据逆序表的概念以及冒泡排序的流程，我们将冒泡排序平均扫描趟数问题转化为逆序表的最大值的问题。

之后我们在逆序表上经过一些组合分析，再结合数学期望的性质，将问题的答案写成了一个和式。于是原问题最终转化为了一个和式的渐近估阶的问题。

然后引用拉马努金Q函数相关的结论，对原和式化简，使得我们可以比较容易地对简化后的和式进行渐近估阶，得到最终结果。

排列的一些基本概念

记 $p = p_{1}p_{2}\cdot\cdot\cdot p_{N}$ 为 $1 \sim N$ 的一个排列。

逆序：一个逆序是 $i < j$ 且 $p_{i} > p_{j}$ 的一个数对。

逆序表：记 $q_{j}$ 表示 $i \in [1..j-1]$ 中 $p_{i} > p_{j}$ 的个数。$q = q_{1}q_{2}\cdot\cdot\cdot q_{N}$ 成为排列 $p$ 的逆序表。

逆序数：记 $\sigma(p) = \sum\limits_{j=1}\limits^{N}q_{j}$，表示排列 $p$ 的逆序数。

排列与逆序表的一一对应

由以上定义可以知道，对于 $1 \leq j \leq N$，$q_{j}$ 需要满足约束 $0 \leq q_{j} < j$。

给定满足该约束的任意一个序列 $q = q_{1}q_{2}\cdot\cdot\cdot q_{N}$，下面我们构造满足该逆序表 $q$ 的排列 $p$。

对于 $i = N, N-1, \cdots, 1$，置 $p_{i}$ 为未曾用过的数中第 $q_{i}$ 大的数，即可从右到左构造 $p = p_{1}p_{2}\cdot\cdot\cdot p_{N}$。

也就是说给定任意长为 $N$ 的逆序表，至少可以构造出一个满足该逆序表的 $1 \sim N$ 的排列，下面我们说明该排列是唯一的。

由于 $q_{i}$ 的取值范围 $[0..i-1]$ 有 $i$ 种可能，因此共有 $N!$ 种可能的逆序表 $q = q_{1}q_{2}\cdot\cdot\cdot q_{N}$。

另一方面我们熟知 $1 \sim N$ 的排列数为 $N!$，如果在 $N!$ 个长为 $N$ 的逆序表中，存在某个逆序表，其对应的排列不唯一，由鸽巢原理，就会出现某个 $1 \sim N$ 的排列对应两个不同的逆序表的情况，这与逆序表的定义矛盾。

因此长度为 $N$ 的排列与逆序表之间存在一一对应关系。这对于我们分析冒泡排序非常有用。

冒泡排序算法

要对一个数组 $p$ 排序，可以重复扫描这个数组。在一趟扫描过程中，假设扫描到 $p[i]$ 时，如果 $p[i] > p[i + 1]$，则将 $p[i]$ 与 $p[i+1]$ 交换，然后扫描下一个。否则直接扫描下一个。

如果在某趟扫描完成时，没有进行过任何交换，也就是每个元素都不比它后面的元素大，则排序就完成了。

由于每个交换都是两个相邻元素的交换，因此交换之后，逆序数减 1，这样总的交换次数恰好是一个排列中的逆序数。

另一方面，通过画图分析我们可以发现，一趟扫描完成后，逆序表中每个非零项的值都会减 1。当逆序表中所有项均为零时，程序结束。

这就隐含了：对一个排列的冒泡排序所需的趟数就等于逆序表中的最大元素。于是冒泡排序平均要跑多少趟，就等同于问：在 $N!$ 种可能的长为 $N$ 的逆序表 $q = q_{1}q_{2}\cdot\cdot\cdot q_{N}$ 中，最大值 $\max\limits_{1\leq j \leq N} q_{j}$ 的平均值是多少。

逆序表中的最大值

对于 $1 \sim N$ 的排列，给定 $0 \leq k \leq N$，考察所有项都小于 $k$ 的逆序表的个数。

考察 $q_{i}$。如果 $i \leq k$，$q_{i}$ 可以取 $[0..i-1]$ 的任意值。当 $i > k$ 时，$q_{i}$ 可以取 $[0..k-1]$ 之间的值。

于是 $N!$ 种长为 $N$ 的逆序表中，所有项都小于 $k$，也就是最大项小于 $k$ 的逆序表的个数为 $k!k^{N-k}$。

因此 $N!$ 个长为 N 的逆序表中，最大项大于等于 $k$ 的概率为 $1 - \frac{k!k^{N-k}}{N!}$。

记 $Q$ 为随机的长为 $N$ 的逆序表中的最大值，于是我们已经得到 $P(Q \geq k) = 1 - \frac{k!k^{N-k}}{N!}$。

下面我们要求 $E[Q]$。这需要用到通过累积分布函数求数学期望的性质。

由累计分布函数求数学期望

我们知道，根据定义计算数学期望的一般方法如下。

$X$ 为离散型，分布律为 $P(X=x)$：

$$E[X] = \sum\limits_{x}xP(X=x)$$

$X$ 为连续型，概率密度函数为 $f(x)$：

$$E[X] = \int xf(x)\mathrm{d}x$$

但如果随机变量 $X$ 非负，还可以有不经过分布律或概率密度函数的算法。

如果非负 $X$ 为离散型，且已知 $P(X \geq n)$，那么有：

$$E[X] = \sum\limits_{n=0}\limits^{\infty}P(X\geq n)$$

证明：

$$\begin{align} E[X] &= \sum\limits_{x=0}\limits^{\infty}xP(X=x) \\ &= \sum\limits_{x=0}\limits^{\infty}\sum\limits_{n=0}\limits^{x}P(X=x) \\ &= \sum\limits_{n=0}\limits^{\infty}\sum\limits_{x=n}\limits^{\infty}P(X=x) \\ &= \sum\limits_{n=0}\limits^{\infty}P(X\geq x) \\ \end{align}$$

$\Box$

类似地，如果非负 $X$ 为连续型，且其累积分布函数为 $F(x)$，那么有：

$$E[X] = \int_{0}^{\infty}(1 - F(x))\mathrm{d}x$$

证明：

$$\begin{align} E[X] &= \int_{0}^{\infty}yf(y)\mathrm{d}y \\ &= \int_{0}^{\infty}\int_{0}^{y}f(y)\mathrm{d}x\mathrm{d}y \\ &= \int_{0}^{\infty}\int_{x}^{\infty}f(y)\mathrm{d}y\mathrm{d}x \\ &= \int_{0}^{\infty}(1 - F(x))\mathrm{d}x \\ \end{align}$$

$\Box$

问题规约：拉马努金Q函数

根据前面对逆序表的分析，以及上述数学期望的性质，长为 $N$ 的逆序表的最大值的期望如下：

$$\sum\limits_{k=0}\limits^{N}(1 - \frac{k!k^{N-k}}{N!}) = N + 1 - \sum\limits_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!}$$

于是最初的问题最终归结到了对 $\sum\limits_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!}$ 的渐近估阶。

对以上和式做下标变换：

$$\sum\limits_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!} = \sum\limits_{k=0}\limits^{N}\frac{(N-k)!(N-k)^{k}}{N!} \\$$

记 $f_{N}(k) = \frac{(N-k)!(N-k)^{k}}{N!}$，下面推导 $f_{N}(k)$：

$$\begin{align} f_{N}(k) &= \frac{(N-k)!(N-k)^{k}}{N!} \\ &= \frac{N-k}{N}\cdot \frac{N-k}{N-1} \cdot\cdot\cdot \frac{N-k}{N-k+1} \\ &= (1 - \frac{k}{N})\cdot (1 - \frac{k-1}{N-1}) \cdot\cdot\cdot (1 - \frac{1}{N-k+1}) \\ &= \prod\limits_{i=1}\limits^{k}(1 - \frac{i}{N-k+i}) \\ \end{align}$$

后续的处理非常复杂，需要对 k 较小和 k 很大的情况分别讨论，比较冗长，其完整推导过程与拉马努金 Q 函数的推导过程类似，这里直接引用结论，如下：

$$\sum\limits_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!} = \sum\limits_{k=0}\limits^{N}f_{N}(k) = \sum\limits_{k=0}\limits^{N}e^{-\frac{k^{2}}{2N}} + O(1) \quad\quad N\rightarrow\infty$$

以后有时间可以再回来看一下上式的推导过程，感兴趣的可以看《算法分析导论》或《计算机程序设计艺术》中关于拉马努金Q函数的内容。

积分逼近求和

下面对 $\sum\limits_{k=0}\limits^{\infty}e^{-\frac{k^{2}}{2N}}$ 进行估阶。记 $h(x) = e^{-\frac{x^{2}}{2N}}$。可以用积分逼近求和：

$$\begin{align} \sum\limits_{k=0}\limits^{\infty}e^{-\frac{k^{2}}{2N}} &= \int_{0}^{\infty}e^{-\frac{x^{2}}{2N}}\mathrm{d}x + \Delta \\ &= \sqrt{2N}\int_{0}^{\infty}e^{-(\frac{x}{\sqrt{2N}})^{2}}\mathrm{d}\frac{x}{\sqrt{2N}} + \Delta \\ &= \sqrt{2N}\int_{0}^{\infty}e^{-t^{2}}\mathrm{d}t + \Delta \\ &= \sqrt{2N}\frac{\sqrt{\pi}}{2} + \Delta \\ \end{align}$$

由于 $h(x)$ 在 $x \geq 0$ 上是单调递减函数，$\Delta \leq |h(0) - h(\infty)| = 1$，于是有：

$$\sum\limits_{k=0}\limits^{\infty}e^{-\frac{k^{2}}{2N}} = \sqrt{\frac{\pi N}{2}} + O(1)$$

上式通过欧拉-麦克劳林公式也可以导出，但由于 $h(x)$ 的单调性，直接用积分逼近求和更简单一些。最终结果为：

$$N + 1 - \sum\limits_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!} = N - \sqrt{\frac{\pi N}{2}} + O(1) \quad\quad N\rightarrow\infty$$

也就是，$N \rightarrow\infty$ 时，冒泡排序平均扫描趟数为 $N - \sqrt{\frac{\pi N}{2}} + O(1)$。

总结

本文我们讨论了排序算法的分析中的一个问题：冒泡排序平均需要跑多少趟。

首先引入了排列中的一些概念定义，包括逆序、逆序表，然后基于冒泡排序的算法流程，发现冒泡排序扫描的趟数就是逆序表中的最大值。

再结合排列的逆序表自身的性质，以及通过累积分布函数求数学期望的性质，最终我们将问题归结到了 $\sum\limits_{k=0}\limits^{N}\frac{k!k^{N-k}}{N!}$ 的渐近估阶。

上式的渐近估阶非常麻烦冗长，我们参考了《计算机程序设计艺术》、《算法分析导论》等名著中关于拉马努金Q函数的相关论述，直接引用结果，将问题转化为 $\sum\limits_{k=0}\limits^{\infty}e^{-\frac{k^{2}}{2N}}$ 的进行估阶。而后者通过积分逼近求和的方式或者欧拉-麦克劳林公式你可以方便解决。

最终我们得出结论，$N \rightarrow\infty$ 时，冒泡排序平均扫描趟数为 $N - \sqrt{\frac{\pi N}{2}} + O(1)$。通过这个例子我们看到，使用拉马努金 Q 函数可以将某些难解的和式简化。

算法分析中使用拉马努金 Q 函数的例子非常多，关于拉马努金 Q 函数的前因后果，以及更多的应用，后续再跟大家探讨。

---