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

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

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

---

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

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

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

首先给出结论，$N\to \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 [\mathrm{1..}j-1]$ 中 $p_i>p_j$ 的个数。$q=q_1{q}_2\cdot \cdot \cdot q_N$ 成为排列 $p$ 的逆序表。

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

排列与逆序表的一一对应

由以上定义可以知道，对于 $1\le j\le N$，$q_j$ 需要满足约束 $0\le 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$ 的取值范围 $[\mathrm{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$ 中，最大值 $\underset{1\le j\le N}{\max }{q}_j$ 的平均值是多少。

逆序表中的最大值

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

考察 $q_i$。如果 $i\le k$，$q_i$ 可以取 $[\mathrm{0..}i-1]$ 的任意值。当 $i>k$ 时，$q_i$ 可以取 $[\mathrm{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\ge k)=1-\frac{k!k^{N-k}}{N!}$。

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

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

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

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

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

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

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

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

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

$$E[X]=\sum _{n=0}^{\infty }P(X\ge n)$$

证明：

$$\begin{array}{rl}E[X]& =\sum _{x=0}^{\infty }xP(X=x)\\ & =\sum _{x=0}^{\infty }\sum _{n=0}^{x}P(X=x)\\ & =\sum _{n=0}^{\infty }\sum _{x=n}^{\infty }P(X=x)\\ & =\sum _{n=0}^{\infty }P(X\ge x)\end{array}$$

$\square$

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

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

证明：

$$\begin{array}{rl}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{array}$$

$\square$

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

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

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

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

对以上和式做下标变换：

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

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

$$\begin{array}{rl}{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 _{i=1}^k(1-\frac{i}{N-k+i})\end{array}$$

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

$$\sum _{k=0}^N\frac{k!k^{N-k}}{N!}=\sum _{k=0}^N{f}_N(k)=\sum _{k=0}^N{e}^{-\frac{k^2}{2N}}+O(1)N\to \infty$$

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

积分逼近求和

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

$$\begin{array}{rl}\sum _{k=0}^{\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{array}$$

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

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

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

$$N+1-\sum _{k=0}^N\frac{k!k^{N-k}}{N!}=N-\sqrt{\frac{\pi N}{2}}+O(1)N\to \infty$$

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

总结

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

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

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

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

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

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