MIT《算法导论》课程第6课《顺序统计与中值》学习笔记.
给出一些无序的元素,找到第k小的元素。
原始方法
排序,并返回A[k]。当k=1时,相当于找最小值;当k=n时,相当于找最大值;当k=$\lfloor \frac{n+1}{2} \rfloor$或$\lceil \frac{n-1}{2}\rceil$时,相当于找中值。
随机的分治算法
参数A, p, q, i
在A[p..q]中找到第i小的元素
1 | def RandSelect(A, p, q, i): |
随机分治分析
假设所有元素互不相等。
幸运的情况:将所有元素按$\frac{1}{10}$,$\frac{9}{10}$划分,则
$$
\begin{align}
T(n) & \le T(\frac{9}{10} n) + \Theta(n) \
& = \Theta(n) \
\end{align} \
(由于n^{\log b a} = n^{\log{9/10} 1} = n^0 = 1)
$$
不幸运的情况:将所有元素按照$0,n-1$划分,则
$$
\begin{align}
T(n) &= T(n-1) +\Theta(n) \
&= \Theta(n^2)
\end{align}
$$
随机分治的预期结果分析
共有n种划分的情况。
令$T(n)$为随机变量,使用指示器随机变量(Indicate Random Variable)定义$X[k],k=0,1,2,\dots,n-1$。
$$
X[k]=\begin{cases}
&1, &分割为k和n-k+1两段 \
&0, &其他
\end{cases}
$$
每一种划分对应一个$X[k]$。
$$
\begin{align}
T(n) & \le \begin{cases}
T(\mathtt{max} { 0,n-1 })+ \Theta(n), &如果以0,n-1划分 \
T(\mathtt{max} { 1,n-2 })+ \Theta(n), &如果以1,n-2划分 \
\vdots \
T(\mathtt{max} { n-1,0 })+ \Theta(n), &如果以n-1,0划分 \
\end{cases} \
& = \sum \limits_{k=0}\limits^{n-1} X_k \left( T(\mathtt{max}{k,n-k-1}) + \Theta(n)\right)
\end{align}
$$
$$
\begin{align}
E[T(n)] &= E\left[\sum \limits_{k=0} \limits^{n-1} (T(\mathtt{max}{k,n-k-1})+\Theta(n))\right] \
&= \sum\limits_{k=0} \limits^{n-1} E \left[ X_k(T(\mathtt{max}{k,n-k-1})+\Theta(n) \right] \
&= \sum\limits_{k=0} \limits^{n-1} E[X_k] \cdot E[T(\mathtt{max}{k,n-k-1})+\Theta(n)] \
&= \frac{1}{n}\sum\limits_{k=0}\limits^{n-1}E[T(\mathtt{max}{k,n-k-1})]+\frac{1}{n}\sum\limits_{k=0}\limits^{n-1}\Theta(n) \
& \le \frac{2}{n}\sum\limits_{k=\lfloor n/2 \rfloor} \limits^{n-1} E[T(k)] + \Theta(n)
\end{align}
$$
下面使用替代法证明上式为$O(n)$。
假设:
$E(T(n)) \le c \cdot n $ 对足够大的常数$c \gt 0$ 成立。
证明:
设$n \le 140$(这是一个魔幻的数)时,$E(T(n)) \le c \cdot n$。
$$
\begin{align}
E[T(n)] &= \frac{2}{n} \sum \limits_{k=\lfloor n/2 \rfloor} \limits^{n-1} E[T(k)] + \Theta(n) \
& \le \frac{2}{n} \sum\limits_{k=\lfloor n/2 \rfloor} \limits^{n-1} c \cdot k + \Theta(n) \
&= \frac{2c}{n} \sum\limits_{k=\lfloor n/2 \rfloor} \limits^{n-1} k + \Theta(n) \
& \le \frac{2c}{n} \cdot \frac{3}{8}n^2 + \Theta(n) \
&= c \cdot n - \left( \frac{1}{4}cn - \Theta(n)\right) \
& \le c \cdot n, 当c足够大时
\end{align}
$$
于是随机选择算法具有$\Theta(n)$的平均时间复杂度,只有在非常不幸运的情况下才会达到$\Theta(n^2)$的时间复杂度。
线性的最坏时间复杂度
关键在于选择一个好的主元(pivot)用于划分。我们可以递归地产生主元。
- Step 1
将元素分为$5 \times \frac{n}{5}$的网络,共$\frac{n}{5}$组,每组5个。(假设恰好够划分,没有多余。)找出每一组元素的中值。这一步用时$O(n)$。
- Step 2
递归地选择$\lfloor n/5 \rfloor$个中值的中值,记为$x$。这一步用时$T(\lfloor n/5 \rfloor)$。
- Step 3
以$x$作为划分的主元进行划分,记$x$的排序号为$k$,即$k= \mathtt{rank} (x)$。
- Step 4
假设我们要找的是第$i$小的元素。
若$i=k$,返回$x$。
若$i \lt k$,递归地在数组的小值区域选择第$k$小的值。
若$i \lt k$,递归地在数组的大值区域选择第$i-k$小的值。
证明它具有线性的最坏时间复杂度
我们不妨设$n \lt 50$时,$T(n) = O(1)$。
对于$n \le 50$,有$3\lfloor n/10 \rfloor \ge \lfloor n/4 \rfloor$。
于是$T(n) \le T(\frac{n}{5}) + T(\frac{3n}{4} + \Theta(n)$。
下面使用替代法证明之。
设$T(n) \le c \cdot n$
则
$$
\begin{align}
T(n) & \le \frac{c}{5}n + \frac{3c}{4}n + \Theta(n) \
&= \frac{19}{20}c \cdot n + \Theta(n) \
&= c \cdot n - \left(\frac{1}{20}cn - \Theta(n)\right) \
&= O(n),如果c足够大
\end{align}
$$
证毕。