# 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，证明过程具体见[这里](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6_046JS15_lec06.pdf)。

### Quicksort

#### Basic Quicksort

**算法**

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

```python
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 的时间复杂度分析](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LRCTZ6z8UV2yPHDcxvZ%2F-LRC_a8EAz4mYORQZ3Qi%2FScreen%20Shot%202018-11-13%20at%2011.00.04%20PM.jpg?alt=media\&token=980965b1-bf85-4913-8aab-40c9b080c04c)

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

#### Pivot Selection Using Median Finding

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

![图 2 - Median Finding + Basic Quicksort 的时间复杂度分析](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LRCTZ6z8UV2yPHDcxvZ%2F-LRCaNrKxVV3Z4s1Lase%2FScreen%20Shot%202018-11-13%20at%2011.03.26%20PM.jpg?alt=media\&token=d556666a-be60-49e0-ab22-6598e4853dd1)

然而由于 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](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LRCTZ6z8UV2yPHDcxvZ%2F-LRCdYUTgwE_vl5-QAfr%2FScreen%20Shot%202018-11-13%20at%2011.17.29%20PM.jpg?alt=media\&token=dc5b55f5-6728-4c04-b40c-402ac6b93f9c)

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

![图 4 - SubProblem Tree](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LRCTZ6z8UV2yPHDcxvZ%2F-LRCeE0Xwi5uNBQBUSKI%2FScreen%20Shot%202018-11-13%20at%2011.20.26%20PM.jpg?alt=media\&token=18081aa6-7252-4036-b5d8-1253761d52ce)

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

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

```
E(#iterations) ≤ 2
```

所以推导公式为：

![图 5 - Paranoid Quicksort Formula](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LRCTZ6z8UV2yPHDcxvZ%2F-LRCf9NiFhfpxKW-U5hk%2FScreen%20Shot%202018-11-13%20at%2011.24.23%20PM.jpg?alt=media\&token=28cd5b19-75d8-446e-acba-3a8cb3453525)

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

## 参考

[video](https://www.youtube.com/watch?v=cNB2lADK3_s\&t=2s)、[lecture note](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6_046JS15_lec06.pdf)

<br>