目录
Random Art
0. Acknowledgement
鸣谢《算法导论》《国家集训队2014论文集》。
1. Monte Carlo Method
1.1. Interesting Facts
- 是在20世纪40年代原子弹发展的背景下发明的。
- 名字源于摩纳哥 Monte Carlo 赌城。
1.2. Definition
2. Las Vegas Algorithm
2.1. Quicksort
快速排序算法（Quick Sort Algorithm） 是最经典的 Las Vegas 算法之一。
2.1.1. Algorithm
分解：数组 A[p ... r] 被划分成两个（可能为空）的子数组 A[p ... q - 1] 和 A[q + 1 ... r]，使得 A[p ... q - 1] 中的每一个元素都小于等于 A[q]，而 A[q] 也小于等于 A[q + 1 .... r] 中的每一个元素。其中，计算下标 q 也是划分过程的一部分。
解决：通过递归调用快速排序，对子数组 A[p ... q - 1] 和 A[q + 1 ... r] 进行排序。
合并：不需要合并操作，A[p ... r] 已经在解决过程有序。
PARTITION(A, p, r)
{
x = A[r];
i = p - 1;
for j = p to r - 1
if A[j] <= x
i = i + 1;
swap(A[i], A[j]);
swap(A[i + 1], A[r]);
return i + 1;
}
QUICKSORT(A, p, r)
{
if p < r
q = PARTITION(A, p, r);
QUICKSORT(A, p, q - 1);
QUICKSORT(A, q + 1, r);
}
partition 在子数组上的时间复杂度是 \(\Theta(n)\)，其中 \(n = r - p + 1\)。
最坏时间复杂度 \(\Theta(n^2)\)，最好时间复杂度 \(\Theta(n\log{n})\)，与本文主题无关，故不解释。
需要说明的是：平衡复杂度为 \(\Theta(n\log{n})\)。
附：随机版的快速排序
RANDOMIZED-PARTITION(A, p, r)
{
i = RANDOM(p, r);
swap(A[r], A[i]);
return PARTITION(A, p, r);
}
RANDOMIZED-QUICKSORT(A, p, r)
{
if p < r
q = RANDOMIZED-PARTITION(A, p, r);
RANDOMIZED-QUICKSORT(A, p, q - 1);
RANDOMIZED-QUICKSORT(A, q + 1, r);
}
2.1.2. Expected Time Complexity
算导证明：9 : 1 划分
咕咕
高中数列推导：（当然我才不管什么下标（
首先有
\[T(n) = n + \frac{1}{n}\sum\limits_{i = 0}^{n - 1}[T(i) + T(n - 1 - i)] \]表示所有划分情况等可能出现。由
\[\sum\limits_{i = 0}^{n - 1}T(i) = \sum\limits_{i = 0}^{n - 1}T(n - 1 - i) \]可化简为
\[T(n) = n + \frac{2}{n}\sum\limits_{i = 0}^{n - 1}T(i) \]错位相减
\[\begin{aligned} &\,\,\,\,\,\,\,nT(n) - (n - 1)T(n - 1) \\ &=n^2 + 2\sum\limits_{i = 0}^{n - 1}T(i) - (n - 1)^2 - 2\sum\limits_{i = 0}^{i - 2}T(i) \\ &=2n - 1 + 2T(n - 1) \\ \iff nT(n) &= (n + 1)T(n - 1) + 2n - 1 \\ \frac{T(n)}{n + 1} &= \frac{T(n - 1)}{n} + \frac{2n - 1}{n(n + 1)} \end{aligned} \]令 \(A(n) = \frac{T(n)}{n + 1}\)：
\[A(n) = A(n - 1) + \frac{2n - 1}{n(n + 1)} \]求出特值 \(T(0) = T(1) = A(0) = A(1) = 0\)。
\(A(n) = \sum\limits_{i = 2}^{n}\frac{2i - 1}{i(i + 1)}, n \ge 2\)。
\[A(n) = \sum\limits_{i = 2}^{n}\frac{2(i + 1) - 3}{i(i + 1)} = \sum\limits_{i =2}^{n}\frac{2}{i} - \sum\limits_{i = 2}^{n}\frac{3}{i(i + 1)} \]调和级数，这是 \(O(\log{n})\) 级的。因此 \(T(n) = (n + 1)A(n)\) 是 \(O(n\log{n})\) 级别的。
2014国家集训队论文推导：（我是不喜欢放缩法的屑（
基本直接搬原文。原文的等号不严谨，但数量级等价，求个大致思路就行了。（说的好像我就很严谨似的)
由于 \(T(n) \ge n\)，所以对于 \(\frac{n}{2} \le i \le j\) 有
\[\begin{aligned} T(i) + T(n - i) \le T(j) + T(n - j) \end{aligned} \]因此
\[\begin{aligned} T(n) &\le n + \frac{2}{n}\sum\limits_{i = n / 2}^{3n / 4}[T(3n / 4) + T(n / 4)] + \frac{2}{n}\sum\limits_{i = 3n / 4}^{3n / 4}[T(n - 1) + T(0)] \\ & \le n + \frac{1}{2}[T(3n/4) + T(n/4)] + \frac{1}{2}T(n - 1) \end{aligned} \]2.2. Minimum Circle Coverage
最小圆覆盖（Minimum Circle Coverage） 算法本质上是一种 随机增量算法（Randomized Incremental Algorithm）。
2.2.1. Algorithm
给出N个点，让你画一个最小的包含所有点的圆。
对于一个最小覆盖圆，满足：
- 该圆唯一。
- 圆上有三个及以上个指定点 或 圆上有两个点分别为该圆直径的两端。
与主题无关，不证。
假设已经求出了 \(i - 1\) 个点的最小覆盖圆，在加入第 \(i\) 个点后，最小覆盖圆一定是以下之一：
- 前 \(i - 1\) 个点中的两个点与第 \(i\) 个点确定的圆。
- 前 \(i - 1\) 个点中的一个点与第 \(i\) 个点为直径作的圆。
由性质推知。
于是可以设计出下面的代码：
center = p[1], r = 0;
// fuko 是执行向量
// check(p1, p2, r) 是判断两点距离是否大于等于 r
// Center(p1, p2, p3) 寻找三点所确定的圆心 联立 3 个圆的方程可解 与主题无关 故请自行实现
for(int i = 2; i <= n; ++i)
{
if(check(center, p[i], r))
continue;
point now; // new center
DB nr = 0; // new radius
for(int j = 1; j < i; ++j)
{
if(check(now, p[j], nr))
continue;
now = (p[i] + p[j]) / 2.0;
nr = fuko.dist(p[i], p[j]) / 2.0;
for(int k = 1; k < j; ++k)
{
if(check(now, p[k], nr))
continue;
now = fuko.Center(p[i], p[j], p[k]);
nr = fuko.dist(now, p[i]);
}
}
center = now;
r = nr;
}
我们痴想 \(n^3\) 直接碾过去。实际上，我们加上 random shuffle，这个算法就实用了。
PS：当时我把 random shuffle 注释了交上去 然后过了）
下证该算法期望时间复杂度。
2.2.2. Expected Time Complexity
\(n\) 个点中最多由三个点确定最小覆盖圆，因此每个点参与确定最小覆盖圆的概率不大于 \(\frac{3}{n}\)。（这里的不参与不是说不枚举）
所以在每一层循环在第 \(i\) 个点调用下一层的概率不大于 \(\frac{3}{i}\)。
设三个循环的复杂度为 \(T_1, T_2, T_3\)，则
\[\begin{aligned} T_1(n) &= O(n) + \sum\limits_{i = 1}^{n}\frac{3}{i}T_2(i) \\ T_2(n) &= O(n) + \sum\limits_{i = 1}^{n}\frac{3}{i}T_3(i) \\ T_3(n) &= O(n) \end{aligned} \]解得 \(T_1(n) = T_2(n) = T_3(n) = O(n)\)。
2.3. Monte Carlo to Las Vegas
对于一类一定有解的构造性问题，假设有一个正确率为 \(p\) 的产生单侧错误的复杂度为 \(O(f(n))\) 的 Monte Carlo 算法。
通过不断运行该算法，直到找到解为止，将其改造成 Las Vegas 算法。
现在来计算改造后的 Las Vegas 算法的运行次数的期望值 \(k\)。
首先这是标准的 几何分布（Geometric Distribution），即 \(P(X = i) = (1 - p)^{i - 1}p, i = 1, 2, 3, \cdots\)。于是
\[\begin{aligned} k &= \sum\limits_{i = 1}^{\infty}(1 - p)^{i - 1}pi = p + \sum\limits_{i = 2}^{\infty}(1 - p)^{i - 1}pi &...(1) \\ (1 - p)k &= \sum\limits_{i = 1}^{\infty}(1 - p)^ipi = \sum\limits_{i = 2}^{\infty}(1 - p)^{i - 1}p(i - 1) &...(2) \\ (1) - (2) \iff pk &= p + \sum\limits_{i = 2}^{\infty}(1 - p)^{i - 1} = \sum\limits_{i = 0}^{\infty}(1 - p)^i = \frac{(1 - p)^0}{p} \\ k &= \frac{1}{p} \end{aligned} \]也即改造后的 Las Vegas 算法期望时间复杂度为 \(O(\frac{1}{p}f(n))\)。
OI Problems
-
Codechef MSTONES
-
P3567 [POI2014]KUR-Couriers
-
CF364D Ghd
-
CF329C Graph Reconstruction
-
Codechef TKCONVEX
-
P1224 [NOI2013] 向量内积