Randomized Algorithms

什么是 Randomized Algorithms

特征:

  • 通过生成随机数来决定算法的走向

  • 同样的输入在不同的执行中可能

    • 运行不同的步骤 (步骤的数量、具体执行内容都可能不同)

    • 产生不同的结果

分类:

  • Monte Carlo: 时间复杂度为 polynomial 以内,结果在大概率(with high probability)情况下正确

  • Las Vegas: 时间复杂度的期望为 polynomial 以内,结果总是正确的。

举例:

Matrix Product Checker

问题描述:

给定 n × n 矩阵 A、B、C,验证 A × B = C 是否成立

普通解法:直接计算 A × B = C

  • Simple Algorithm: O(n^3) multiplications

  • Strassen: multiply two 2 × 2 matrices in 7 multiplications: O(n^2.81)

  • Coppersmith-Winograd: O(n^2.376)

可以做到 O(n^2) 吗?

Frievald's Algorithm (Monte Carlo)

本算法能够做到:

  • 如果 A × B = C,那么 Pr[output=YES] = 1

  • 如果 A × B ≠ C,那么 Pr[output=YES] ≤ 1/2,即 False Positive Rate

这样,若 k 次运行结果都是 YES,那么 False Positive 的概率将达到 (1/2)^k,因此这是一个 Monte Carlo 算法。

过程:

任意选择一个二值向量 r,向量中的每个元素都以 1/2 的概率取值为 1,1/2 的概率取值为 0 。如果 A(Br) = Cr,输出 YES,否则输出 NO

分析:

只要证明所有的二值向量中,至多有一半能在 A × B ≠ C 的情况下,使得 output=YES,证明过程具体见这里

Quicksort

Basic Quicksort

算法

始终选择 A[1] 或 A[n] 作为 pivot

def quicksort(A, start=1, end=n):
m = partition(A) # O(n)
quicksort(A, start, m-1)
quicksort(A, m+1, end)
def partition(A):
pivot = A[1]
# ...

分析

如果输入是已经顺序或逆序,partition 会将所有元素放在 pivot 的同一边,此时:

图 1 - Basic Quicksort 的时间复杂度分析

空间复杂度在 in-place 情况下可做到 O(1)

Pivot Selection Using Median Finding

使用 Median Finding 算法可以保证在 θ(n) 时间复杂度下,获得数组的中位数,这样每次 partition 都能完美地将数组分成两部分,此时:

图 2 - Median Finding + Basic Quicksort 的时间复杂度分析

然而由于 Median Finding 较为复杂,虽然时间复杂度在 θ(n),但常数项较大,在实际运用中并不适用,通常要逊色于 mergesort。

Randomized Quicksort (Las Vegas)

使用随机选取任意元素作为 pivot 的策略,时间复杂度的期望为 O(nlgn),分析见 CLRS p.181-184。本课尝试分析该算法的一个变种:Paranoid Quicksort

"Paranoid" Quicksort (Las Vegas)

Good/Bad Pivots

图 3 - Good/Bad Pivots

可以看出选中 good pivot 的概率≥ 1/2,而 good pivot 中最差的两个分别在交界处,若选中它,问题将被分成大小分别为 (1/4)n 及 (3/4)n 的子问题。使用问题树分析:

图 4 - SubProblem Tree

本图有一定的误导性,实际上这是一个不平衡的树,树的深度从左往右逐渐递增。

由于选中 good pivot 的概率≥ 1/2,因此每次 pivot selection 执行的次数的期望:

E(#iterations) ≤ 2

所以推导公式为:

图 5 - Paranoid Quicksort Formula

从图中可以看出,树的高度最高位 log(4/3)(2cn),因此最终时间复杂度的期望 T(n) = θ(nlgn)。

参考

videolecture note