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)。
参考
​video、lecture note​

MIT - 6.001 - SICP - Previous

内存管理

Next - MIT - 6.046

Skip Lists

Last modified 3yr ago

Copy link

Outline

什么是 Randomized Algorithms

特征：

分类：

举例：

Matrix Product Checker

Quicksort

参考