指示变量法

2025-03-26

0. 引入

根据期望的线性性：

那么，就可以通过找到而计算，一般地，有三个条件：

能够找到这样的分解
计算比直接计算容易
计算出后，对求和容易，即计算容易，特别地，若，则

条件 3 不必总是满足，有时没有封闭表达式，但能够渐进分析。

对于事件，定义其指示变量

立刻有

如果能找到一系列事件，满足，则

那么只需容易计算，条件 2 自然满足。

1. 逆序数

数列是集合的等概随机排列，表示在数列中的位置，是到的双射，实际上

逆序对是满足且的数对，逆序数是逆序对的总数，求逆序数的期望值。

考虑每对元素是否形成了逆序对，例如的位置是否在的位置之后。

令

表 示

则由对称性，

逆序对总数：

所以：

2. 快速排序 1

研究随机化的快速排序：对于每一个子问题，等概随机地选择主元。我们希望研究这个随机算法所选主元总数的期望。

快速回顾一下快速排序算法，可以知道每个元素最多被选为主元一次。如果某个元素从未被选为主元，那么大小上相邻的元素一定被选为了主元。因此，一共至少个主元，最多可能需要个主元，那么期望一定介于和之间。

简化模型，设被排序的数列是集合的等概随机排列。

设随机变量为主元总数，事件为 “ 被选为主元”，是的指示变量，那么

一个有用的观点是：随机化快速排序等价于给每个元素一个随机优先级；在任意子区间中，优先级最高的元素最先成为主元。

则不是主元等价于在中优先级最低。

故

3. 快速排序 2

注：本节内容改自 SJTU CS1212 slides

问题

现在研究快速排序的时间复杂度。

快速排序的时间复杂度主要来源于比较元素，因此可以用比较的总次数衡量一次快速排序算法运行的时间。类似逆序对，总次数可以分解为每对元素的比较次数，即

设被排序的数列是集合的等概随机排列。

基本事实

下面给出几个事实：

对于，某个轮次中与产生比较，等价于或是当轮的主元，且任意满足的都尚未被选为主元，否则和已经被分开
对于，由于与终要分开，要么被其他主元分开，要么两者直接比较。所以等价于任意满足的都未被选为主元，直到或成为主元，也就等价于，或是中最先成为主元的。

把“ 或是中最先成为主元的”作为事件，这就是说是的指示变量。

计算

对于这个结果，可以作渐进分析，得到快速排序时间复杂度的经典结论：

4. 最小元素

问题

从集合中，等概随机地选择大小为的子集，求子集最小元素的期望

直接计算

记子集最小元素为随机变量

进一步处理这个式子比较困难，下面展示指示变量法如何巧妙解决问题。

方法 1

令事件表示，指示变量为

那么，

换元，令

方法 2

可以证明原问题与下面的问题等价：

序列的前 k 个元素是，后个元素是，是的等概随机排列，映射函数是，设中的最小位置为随机变量，形式化地，

求