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 的同一边，此时：

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

Pivot Selection Using Median Finding

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

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

Randomized Quicksort (Las Vegas)

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

"Paranoid" Quicksort (Las Vegas)

Good/Bad Pivots

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

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

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

E(#iterations) ≤ 2

所以推导公式为：

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

参考

video、lecture note

Previous内存管理NextSkip Lists

Last updated