一、问题描述 假设数列 B={} 是由 n 个不重复的数字按从小到大有序排列得到的，有序数列 B 是未知的，仅方便后续分析描述，数列 A={} 由数列 B 随机重排列得到，现使用小顶堆算法求数列 A 的第 k 个最大的数，求算法的平均时间复杂度。 二、算法分析 算法总体分为两个阶段：“堆初始化”与“堆更新”，依次对两个阶段进行分析： 阶段1：选取数列 A 的前 k 个数字进行堆的初始化，设该堆的初始最小值为 ，可知 M 有 n-k+1 种可能，分别为 1、2、3 …… n-k+1，现计算每种可能出现的概率 P{M=m}： 易知从 n 个数字中随机选取 k 个数字，共有 种可能； 大于 的...
