序统计量

概述

序统计量 是集合中第 $i$ 小的元素。最小值（$i=1$）和最大值（$i=n$）是序统计量的特例，而选择问题可以在 $\Theta (n)$ 时间内解决。

定义

序统计量

给定一个包含 $n$ 个（互异）元素的集合 $S$ 和一个整数 $i$（$1\le i\le n$），第 $i$ 序统计量（$i$-th order statistic）是 $S$ 中恰好有 $i-1$ 个元素小于或等于它的元素。

• 当 $i=1$ 时，序统计量为最小值（minimum）。
• 当 $i=n$ 时，序统计量为最大值（maximum）。
• 当 $i=\lfloor (n+1)/2\rfloor$ 时，序统计量为中位数（median），也称下中位数。

核心性质

• 中位数是最常用的序统计量，它将集合分为大小相等的两部分。
• 选择问题（selection problem）可以在 $\Theta (n)$ 时间内解决，无需先排序（排序需要 $\Theta (n\lg n)$）。
• 最小值和最大值可以通过 $n-1$ 次比较找到；同时找到两者只需 $\lceil 3n/2\rceil -2$ 次比较。
• 序统计量是非参数统计的基础概念，不依赖数据分布假设。

章节扩展

第9章：中位数与序统计

• 9.1 最小值和最大值 最小值和最大值是序统计量的特例，可在 $\Theta (n)$ 时间内找到。
• 9.2 期望线性时间选择 RANDOMIZED-SELECT 基于快速排序的 PARTITION，期望 $\Theta (n)$。
• 9.3 最坏情况线性时间选择 SELECT（BFPRT）算法通过中位数的中位数保证最坏 $\Theta (n)$。

参见

• 中位数