题解 UVA12004 【Bubble Sort】

· · 题解

前言

给出一种与诸多题解不同的做法，启发来自《算法导论》，并采用书中的一些记号。

约定

分析

首先，题目可以被转化成求期望逆序对数的模型，这是显然的。

引进随机变量指示器 \text{(indicator random variable)} 这一概念。给定一个样本空间 S 和一个事件 A，定义 A 事件对应的随机变量指示器为：

I\{A\}= \begin{cases} 0,\text{if A don't happen} \\ 1,\text{if A happen} \end{cases}

那么，我们现在定义 X_{i,j} 为 T 事件的随机变量指示器，其中 T 事件为随机序列 a 中 i<j\wedge a_i>a_j，形式化的说，有 X_{i,j}=I\{T\}。那么序列 a 的逆序对数 X=\sum\limits_{i<j} X_{i,j}。事实上从 \text{OI} 不严谨的角度，可以把它理解成一个 0/1 变量，即 \text{bool} 变量。

现在我们对 X=\sum\limits_{i<j} X_{i,j} 两边同时取期望，就得到 E[X]=E\left[\sum\limits_{i<j} X_{i,j}\right]，E[X] 就是所求，期望逆序对数。

又有期望的线性性质 E[X+Y]=E[X]+E[Y]，于是有

E[X]=\sum_{i<j}E[X_{i,j}]=\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}E[X_{i,j}] \ \ \ \ \ 1.1

到这里似乎还是常规的期望相关，那么在求解过程中为什么要引入 \text{indicator random variable} 这个新概念呢？下引书中原文。

powerful analytical technique;} \text{it applies even when there is dependence among the random variables. ---’Introduction to the Algorithm',Chapter 5.2}

翻译成中文就是“期望的线性性质利用指示器随机变量作为一种强大的分析技术；当随机变量间存在依赖关系时也仍旧成立“。对于这一断言，读者可以自行证明。

上述问题中的 X_{i,j} 显然存在依赖关系，但因为引入了指示器随机变量这一概念并有了这一强有力的断言，使得我们能够将 \forall i<j 的 E[X_{i,j}] 独立看待。那么，我们现在可以得出，对于 \forall i,j，E[X_{i,j}] 的值是一样的，并且尝试去计算这个值。

对于任意 X_{i,j} 都是一个指示器随机变量，其值非 0 即 1。根据期望的定义，它的期望值就是 Pr\{T\}，即 T 事件发生的概率。现在只需求出 Pr\{T\} 便可解决整个问题。显然有：

X_{i,j}=Pr\{T\}=\frac{\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i-1}1}{\left(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^n 1\right)-n}=\frac{\frac{n(n-1)}{2}}{n(n-1)}=\frac{1}{2} \ \ \ \ \ 1.2

回带至 1.1 式，得：

E[X]=\sum_{i=1}^{n}\sum_{j=i+1}^nE[X_{i,j}]=\sum_{i=1}^{n}\sum_{j=i+1}^n\frac{1}{2}=\frac{n(n-1)}{4}

后言

这就是很多人推出的那个式子。

总结一下，这种做法的亮点在 1.2 式。通过破除随机变量间的依赖性，从而快速求解问题是引入 \text{indicator random variable} 的优势，可能很多 \text{Oier} 觉得很暴力。但怎么说呢，暴力即优美吧（大雾

其实可能很多人也知道这种做法，但是不知道其背后的理论基础，所以说还是要多读点 \text{CS} 基础书籍啊（