关于使用小顶堆解决Top K问题的平均时间复杂度分析

寻找第K大

https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf?tpId=295&tqId=44581&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj

一、问题描述
假设数列 B={ $b_n$ } 是由 n 个不重复的数字按从小到大有序排列得到的，有序数列 B 是未知的，仅方便后续分析描述，数列 A={ $a_n$ } 由数列 B 随机重排列得到，现使用小顶堆算法求数列 A 的第 k 个最大的数，求算法的平均时间复杂度。

二、算法分析
算法总体分为两个阶段：“堆初始化”与“堆更新”，依次对两个阶段进行分析：

阶段1：选取数列 A 的前 k 个数字进行堆的初始化，设该堆的初始最小值为 $b_M$ ，可知 M 有 n-k+1 种可能，分别为 1、2、3 …… n-k+1，现计算每种可能出现的概率 P{M=m}：
$\qquad$ 易知从 n 个数字中随机选取 k 个数字，共有 $C_n^k$ 种可能；
$\qquad$ 大于 $b_m$ 的数字共 n-m 个，则随机选取 k 个数字，最小值恰好为 $b_m$ 的情况共 $C_{n-m}^{k-1}$ 种；
$\qquad$ 每种选取结果均等可能出现，满足古典概型，则有：
$\begin{equation} P\{M=m\}=\frac{C_{n-m}^{k-1}}{C_n^k}\\ \end{equation}$

阶段2：完成堆的初始化后，需要逐个将数列 A 剩余的 n-k 个元素和堆顶元素 $b_m$ 进行比较，如果数列元素大于堆顶元素，则将之插入堆中进行更新，否则忽略该元素。可知算法的效率取决于更新操作发生的次数 C，而更新操作发生的次数又取决于比 $b_m$ 大的元素的排列情况（设该排列为 G={ $g_{n-m-k＋1}$ }，因为其中 k-1 个在初始化阶段就已经处于堆中，所以更新阶段比 $b_m$ 大的只有 n-m-k+1 个），在 G 的所有可能排列下，堆的更新次数的期望为调和级数的值，证明如下：

$\qquad$ 设数列 G 由 t 个不重复元素随机排列组成，易知 G 共有 $t!$ 种可能，其触发堆更新的次数C的期望设为 $E_t(C)$ ，在所有可能的排列中，能够触发s次堆更新的排列设有 $h_t(s)$ 种，所有排列触发更新的次数总和设为 $S(t)$ ，有：
$\begin{equation} \displaystyle\sum_{s=1}^t h_t(s)=t!\\ \end{equation}$
$\begin{equation} \displaystyle\sum_{s=1}^t s\cdot h_t(s)=S(t)\\ \end{equation}$
则随机数列 G 触发堆更新的期望可以表示为：
$\begin{equation} E_t(C)=\displaystyle\sum_{s=1}^t s\cdot \frac{h_t(s)}{t!}=\frac{S(t)}{t!}\\ \end{equation}$
现在尝试建立从 $E_{t-1}(C)$ 到 $E_t(C)$ 的递推关系式，从而求解出表达式：可以想到，t个元素组成的数列是由 t-1 个元素的数列插入一个新元素得到的，不妨设该元素为值最小的元素 $g_0$ （因为我们对数列内容没有额外限制，所以这种假设是合理的，实际上这个元素可以是任意一个元素，而取最小值则有利于分析），下面讨论插入的情况：
$\qquad$ 将其插入到原数列的第0号位置（数列头部），此时新数列触发次数增加了1，因为该元素不会“屏蔽”后面的元素，也没有元素会去“屏蔽”它， $g_0$ 在0号位置的所有排列触发次数总和为 $S(t-1)＋(t-1)!$ ；
$\qquad$ 将其插入到原数列的第 i 号位置（非数列头部，一共有 t-1 种可能），此时新数列触发次数与原数列相同，因为该元素不会“屏蔽”后面的元素，但是前面的元素会去“屏蔽”它（比它大）， $g_0$ 在第 i 号位置的所有排列触发次数总和为 $S(t-1)$ ；
$\qquad$ 那么我们就能得到：
$\begin{equation} S(t)=1\cdot [S(t-1)＋(t-1)!]＋(t-1)\cdot S(t-1)\\=t\cdot S(t-1)＋(t-1)!\\ \end{equation}$
$\begin{equation} E_t(C)=\frac{S(t)}{t!}=\frac{t\cdot S(t-1)＋(t-1)!}{t!}=E_{t-1}(C)＋\frac{1}{t}\\ \end{equation}$
即：
$\begin{equation} E_t(C)=\displaystyle\sum_{i=1}^t\frac{1}{i}\\ \end{equation}$

将该结论应用到Top K问题中（特殊地，当 m=n-k+1 时更新次数为0），有：
$\begin{equation} E_{M=m}(C)=\begin{cases}\displaystyle\sum_{i=1}^{n-m-k＋1}\frac{1}{i},\,\,m<n-k＋1\\0,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,m=n-k＋1\\ \end{cases}\\ \end{equation}$
那么，对于由同一有序数列 B 经过随机排列得到的所有不同数列 A，运用小顶堆算法求解 Top K 问题时，堆的平均更新次数 C 为：
$\begin{equation} E(C)=\displaystyle\sum_{m=1}^{n-k＋1}P\{M=m\}E_{M=m}(C)\\ =\displaystyle\sum_{m=1}^{n-k}\frac{C_{n-m}^{k-1}}{C_n^k}\displaystyle\sum_{i=1}^{n-m-k＋1}\frac{1}{i}\\ \end{equation}$

考虑到调和级数没有通项公式，而组合数有不少可以化简的技巧，所以尝试调换内外求和的顺序，将上述二重求和表达式展开，得到：

自变量公共项 i＝1 i＝2 i＝3 ··· i＝n－k－1 i＝n－k

m=n-k	$\frac{C_k^{k-1}}{C_n^k}$	1	$\times$	$\times$	...	$\times$	$\times$
m=n-k-1	$\frac{C_{k＋1}^{k-1}}{C_n^k}$	1	$\frac{1}{2}$	$\times$	...	$\times$	$\times$
m=n-k-2	$\frac{C_{k＋2}^{k-1}}{C_n^k}$	1	$\frac{1}{2}$	$\frac{1}{3}$	...	$\times$	$\times$
...	...	...	...	...	...	...	...
m=2	$\frac{C_{n-2}^{k-1}}{C_n^k}$	1	$\frac{1}{2}$	$\frac{1}{3}$	...	$\frac{1}{n-k-1}$	$\times$
m=1	$\frac{C_{n-1}^{k-1}}{C_n^k}$	1	$\frac{1}{2}$	$\frac{1}{3}$	...	$\frac{1}{n-k-1}$	$\frac{1}{n-k}$

调换求和次序，将 m 作为内层求和变量，i 作为外层求和变量，得到：
$\begin{equation} E(C)=\displaystyle\sum_{m=1}^{n-k}\frac{C_{n-m}^{k-1}}{C_n^k}\displaystyle\sum_{i=1}^{n-m-k＋1}\frac{1}{i}\\=\displaystyle\sum_{i=1}^{n-k}\frac{1}{i}\displaystyle\sum_{m=1}^{n-k＋1-i}\frac{C_{n-m}^{k-1}}{C_n^k}\\ \end{equation}$
注意到（对下式进行展开，并利用凑项技巧，使得组合数的加法性质得以应用）：
$\begin{equation} \displaystyle\sum_{m=1}^{n-k＋1-i}C_{n-m}^{k-1}=C_n^k-C_{k＋i-1}^k\\ \end{equation}$
那么：
$\begin{equation} E(C)=\displaystyle\sum_{i=1}^{n-k}\frac{1}{i}\frac{C_n^k-C_{k＋i-1}^k}{C_n^k}\\=\displaystyle\sum_{i=1}^{n-k}\frac{1}{i}-\displaystyle\sum_{i=1}^{n-k}\frac{1}{i}\frac{C_{k＋i-1}^k}{C_n^k}\\ \end{equation}$
又注意到（将下列组合数展开为阶乘形式可得等式）：
$\begin{equation} \frac{C_{k＋i-1}^k}{i}=\frac{C_{k＋i-1}^{k-1}}{k}\\ \end{equation}$
那么：
$\begin{equation} E(C)=\displaystyle\sum_{i=1}^{n-k}\frac{1}{i}-\displaystyle\sum_{i=1}^{n-k}\frac{1}{k}\frac{C_{k＋i-1}^{k-1}}{C_n^k}\\=\displaystyle\sum_{i=1}^{n-k}\frac{1}{i}-\frac{1}{kC_n^k}\displaystyle\sum_{i=1}^{n-k}C_{k＋i-1}^{k-1}\\ \end{equation}$
借助同样的凑项化简组合数技巧，得：
$\begin{equation} E(C)=\displaystyle\sum_{i=1}^{n-k}\frac{1}{i}-\frac{C_n^k-1}{kC_n^k}\\ \end{equation}$
其中 $\frac{C_n^k-1}{kC_n^k}$ 的值小于1，可以忽略不计，而调和级数有近似公式，n 越大时越精确：
$\begin{equation} \displaystyle\sum_{i=1}^n\frac{1}{i}\approx ln(n＋1)＋0.5772\\ \end{equation}$

故：
$\begin{equation} E(C)\approx ln(n-k＋1)＋0.5772\\ \end{equation}$

上述表达式是堆更新操作发生的次数期望，则堆不发生更新的期望便为： $n-k-E(C)$ ，而堆进行一次更新的复杂度为 $log(k)$ ，不更新的复杂度为 1，堆初始化的复杂度为 k，故算法整体的复杂度为：
$\begin{equation} O_k(n)\approx E(C)log(k)＋(n-k-E(C))\cdot 1＋k\\\approx ln(n-k＋1)log(k)＋n\\ \end{equation}$

========== 全 === 文 === 完 ==========