open-courses
Search…
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)。

参考