中位数

概述

中位数 是 $i=\lfloor (n+1)/2\rfloor$ 时的序统计量，即将有序集合分为大小相等（或相差1）的两部分的元素。它比均值更鲁棒，是工程实践中最常用的集中趋势度量之一。

定义

中位数

给定一个包含 $n$ 个元素的集合 $S$，下中位数（lower median）是第 $\lfloor (n+1)/2\rfloor$ 序统计量，上中位数（upper median）是第 $\lceil (n+1)/2\rceil$ 序统计量。当 $n$ 为奇数时两者相同；当 $n$ 为偶数时，中位数通常取两者的平均值。

• CLRS 主要讨论下中位数，即 $i=\lfloor (n+1)/2\rfloor$。

核心性质

• 鲁棒性：中位数不受极端值（outlier）影响，比均值更稳健。例如，数据集 $\{1,2,1000\}$ 的均值是 334.3，但中位数是 2。
• 工程实践：P50（中位数）、P95、P99 是 SRE（站点可靠性工程）中衡量延迟和性能的核心指标。
• 分治关键：中位数将集合精确地分为两半，这使得它在分治算法中具有天然优势。
• 中位数可以在 $\Theta (n)$ 时间内找到（无需排序），这是选择算法的核心成果。

章节扩展

第9章：中位数与序统计

• 9.1 最小值和最大值 中位数是序统计量的特例。
• 9.2 期望线性时间选择 RANDOMIZED-SELECT 可以高效地找到中位数。
• 9.3 最坏情况线性时间选择 SELECT 算法通过递归找中位数的中位数来保证最坏情况线性时间。

参见

• 序统计量