顺序统计与中值学习笔记

Posted on

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
2
3
4
5
6
7
8
9
10
11
def RandSelect(A, p, q, i):
  if p == q:
    return A[p]
  r = RandPartition(A, p, q) # 随机分治
  k = r - p +1               # k是划分元素的序号
  if i == k:                 # k是要找的序号
    return A[r]     
  if i < k:
    return RandSelect(A, p, r - 1, i) # 在左边找
  else:
    return RandSelect(A, r + 1, q, i - k) # 在右边找

随机分治分析

假设所有元素互不相等。

幸运的情况：将所有元素按$\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}
$$

证毕。