还没写完。
这个东西也许和 OI 有关？反正也要复习，干脆写篇博客。
introduction
传统算法设计一般考虑有效算法（多项式时间），以及追求“精确解”，尤其是“经典”算法或者数据结构。这节课一般考虑那些不那么传统的、更加偏向现代的算法设计。
一种就是近似算法，比如探索 NP-hard 问题在多项式时间内可以近似到多么精确，或者是本来存在多项式时间算法的问题，能否使用近似解改良复杂度。
对于最小化问题，一般使用近似比来衡量一个解的质量，如果对于某个输入 \(I\)，你得到的解为 \(\mathrm{ALG}(I)\) 而最优解为 \(\mathrm{OPT}(I)\)，那么我们可以通过 \(\max_{I}\frac{\mathrm{ALG}(I)}{\mathrm{OPT}(I)}\) 来衡量你给出的解的质量，这个值的取值范围显然是 \([1,+\infty)\)，越小说明质量越好。
称该算法是 \(\alpha-\) 近似的，当对任意 \(I\)，都有 \(\mathrm{ALG}(I)\le \alpha \cdot \mathrm{OPT}(I)\)。
例如 TSP 问题（旅行商问题，就是经过所有点并且回到出发地的最短长度），找到最小生成树上的最优解就是一个 \(2-\) 近似算法；找平面点集直径随便选择一个点然后找到离这个点最远的也是一个 \(2-\) 近似算法。
另一种意义上的近似是算法本身具有随机性，对于确定的输入得到随机的输出，比如有一定概率出错，但是不出错时有很好的性能保证。
近似 + 随机是现代算法设计的大趋势。
random
随机数
要在程序中生成随机数，可以考虑 C++ 中的 random 库，预设的几个标准随机数生成器如基于线性同余的 minstd_rand0 、 minstd_rand 和 knuth_b，基于 Mersenne Twister 的 mt19937 ，还有基于 Lagged Fibonacci 的 ranlux24 和 ranlux48，一般使用 minstd_rand 就行了。
然后还有从很多不同的特殊分布中采样，例如均匀独立采样 uniform_int_distribution 和 uniform_real_distribution 分别是在一个区间里面均匀采整数或者实数，其他例如两点分布的 bernoulli_distribution 以 \(p\) 的概率取 \(1\) 其余取 \(0\)，还有二项分布 binomial_distribution ，另外一个较常用到的是正态分布（高斯分布） normal_distribution 。
例如下面程序可以生成 \(10\) 个从标准正态分布 \(\mathcal{N}(0,1)\) 中的采样。
#include<random>
using namespace std;
int main(){
std::minstd_rand gen(114514);
std::normal_distribution<double> dis(0.0,1.0);
for(int i=1;i<=10;++i)
printf("%.5lf\n",dis(gen));
return 0;
}
而更加一般的离散分布采样就是 discrete_distribution ，例如下图：
#include<random>
using namespace std;
int main(){
std::minstd_rand gen(114514);
std::discrete_distribution<> dis({1,4,6,4,1});
for(int i=1;i<=10;++i)
printf("%d\n",dis(gen));
return 0;
}
这里传入的参数是一个长度为 \(n\) 的数组 \(a\)，下标从 \(0\) 到 \(n-1\)，其中 \(i\) 数字生成的概率为 \(\frac{a_i}{\sum_{j=0}^{n-1}a_j}\)。
随机算法
考虑一个随机算法，如果有 \(\delta\) 的出错概率，也就是说正确概率为 \(1-\delta\)，如果算法只需要运行一次 \(\delta\) 取足够小的常数就行了，如果要多次运行且每次成功，可能就需要让 \(\delta\) 与运行次数相关。如果运行 \(q\) 次且每次失败概率为 \(\delta\)，根据 Union Bound \(\mathrm{Pr}[\bigcup_i X_i]\le \sum_i \mathrm{Pr}[X_i]\)，那么存在一次失败概率至多 \(q\delta\)。
算法具体分析的时候也许需要用到各种理论推导得出需要运行的次数，但是实际上只要试试够用就行了。
一些典型随机算法
测试矩阵相乘结果是否正确
给定三个 \(n\times n\) 的矩阵 \(A,B,C\)，问是否有 \(AB=C\)。
考虑生成一个长度为 \(n\) 的随机向量 \(x\)，每个值从集合 \(\{0,1\}\) 中等概率选取，如果 \(AB=C\) 那么必须有 \(ABx=Cx\)，如果 \(AB\ne C\)，那么考虑 \(AB\) 和 \(C\) 中至少有一列不完全相同，不妨假设是第 \(t\) 列，先确定 \(x\) 其他位置的值，然后考虑 \(t\) 位置的值，容易发现 \(t=0\) 和 \(t=1\) 中至少有一个会导致 \(ABx\ne Cx\)，所以可以看出此时 \(ABx\ne Cx\) 的概率不低于 \(0.5\)。
重复随机 \(T\) 次，那么容易发现出错概率不超过 \(0.5^T\)，更一般地，如果有一次出错概率 \(p\le 0.5\)，那么 \(T\) 次都出错的概率就是 \(p^T\)，要有 \(\delta\) 的出错概率或者说 \(1-\delta\) 的成功率就只需要有 \(T=O(\log (1/\delta))\) 即可。
\(\delta\) 取常数的话这个算法便可以做到 \(O(n^2)\) 判断。
Median Trick
现在有⼀个⿊盒能以 \(p>0.5\) 的概率正确回答某个 Yes/No 问题的答案，能否将其强化成任意的 \(1-\delta\)？
同样的，重复随机 \(T\) 次，取出现次数较多的作为答案，要选多大才行？
Chernoff Bound：设独立随机变量 \(X_1,\dots,X_n\in [0,1]\)，令 \(X=\sum_{i=1}^nX_i,\mu=\mathrm{E}[X]\)，则对 \(t\in [0,1]\) 有 \(\mathrm{Pr}[|X-\mu|\ge t\mu]\le 2\exp(-t^2\mu/3)\)。
随机 \(T\) 次回答正确次数期望时 \(pT\)，所以也就要使得 \(\mathrm{Pr}[|X-pT|\ge (p-0.5)T]\le \delta\)，视 \(p\) 为常数容易发现 \(T\) 取到 \(O(\log (1/\delta))\) 即可。
Hoeffding inequality：设独立随机变量 \(X_1,\dots,X_n\in [a,b]\)，令 \(X=\sum_{i=1}^nX_i,\mu=\mathrm{E}[X]\)，则对任意 \(t\) 有 \(\mathrm{Pr}[X-\mu\ge t]\le 2\exp\left(-\frac{2t^2}{n(b-a)^2}\right)\)。
recursion（递归）
这里是介绍经典算法，没啥好说的（）
hash
哈希算法
\(h:[n]\to[m]\) 是随机哈希，指对于每个 \(i\in [n]\)，有 \(h(i)\) 是 \([m]\) 上的均匀随机分布。一般要求是对于 \(i\ne j\)，有 \(\mathrm{Pr}[h(i)=h(j)]\le 1/m\)，其中每个 \(j\in [m]\) 称为 bucket。
考虑分布式环境的负载均衡问题，有 \(n\) 个请求要丢给 \(m\) 台服务器处理，如何使得每台服务器处理的请求个数尽量平均？可以使用上面讲到的随机哈希。
那么如果需要新增服务器呢？重构哈希函数太麻烦。
可以使用一致性哈希算法：构造一个足够大的哈希函数 \(h:\mathrm{int} \to \mathrm{int}\)，然后把请求和服务器都哈希一下到一个环上，然后每个请求丢给这个环上对应后面第一个服务器做，只需要一个支持增删和查询后继操作的有序表即可。可以证明大概率负载均衡。
Count-min Sketch
考虑这样一个问题：输入 \(N\) 个 \([n]\) 上的整数，输入结束后给定 \(i\)，要求近似回答 \(i\) 出现的次数。
Count-min Sketch 是一个数据结构，支持对于任意的误差参数 \(\epsilon\in (0,1)\)，满足插入 \(N\) 个 \([n]\) 上的元素后给定 \(x\in[n]\) 查询 \(x\) 共出现多少次，设 \(\tilde{C}\) 表示估计量，\(C\) 表示真实量，可以以大概率（\(1-1/\mathrm{poly}(n)\) 的概率）满足 \(C\le \tilde{C}\le C+\epsilon\cdot N\)。
空间使用 \(\frac{\mathrm{poly}\log n}{\epsilon}\)，且单次查询和插入单个元素的时间为 \(\frac{\mathrm{poly}\log n}{\epsilon}\)。
大体思路就是设置一个随即哈希函数 \(h:[n]\to [m]\)，然后对每一个 \(j\in [m]\) 统计 \(C[j]\) 为满足 \(h(x)=j\) 的数量。容易发现如果不存在哈希冲突最后 \(C[h(x)]\) 就是 \(x\) 出现次数，如果出现冲突那么 \(C[h(x)]\) 只会更大。
设 \(x\) 真实出现次数为 \(C_x\)，那么有：
\[\begin{aligned} \mathrm{E}[C[h(x)]]&=\mathrm{E}\left[C_x+\sum_{y\ne x,h(y)=h(x)}C_y\right]\\ &=C_x+\sum_{y\ne x,h(y)=h(x)}C_y\\ &=C_x+\sum_{y\ne x}\mathrm{Pr}[h(x)=h(y)]C_y\\ &\le C_x+N/m \end{aligned} \]Markov inequality：若 \(X\ge 0\)，有 \(\mathrm{Pr}[X\ge a]\le \mathrm{E}[X]/a\)。
对 \(C[h(x)]-C_x\) 用 Markov inequality，有 \(\mathrm{Pr}[C[h(x)]-C_x> \epsilon\cdot N]\le \frac{N/m}{\epsilon\cdot N}\le \frac{1}{\epsilon m}\)，这里令 \(m\) 取 \(\frac{2}{\epsilon}\) 即可得到 \(0.5\) 的概率满足条件。
由于 \(C[h(x)]\) 总是高估，可以多次实验取最小值，每次至少 \(0.5\) 概率满足条件，所以独立运行 \(O(\log n)\) 次即可以 \(1-1/\mathrm{poly}(n)\) 的概率满足条件。
所以整体思路就是设置 \(T=O(\log n)\) 个独立随机哈希 \(h^{(i)}:[n]\to [m]\)，其中 \(m=2/\epsilon\)，并初始化 \(T\) 个 \(m\) 元 counter，然后插入删除元素就在每个 counter 里面都做就行了，查询就返回所有 counter 对应位置的最小值。
并且可以发现由于我们仅仅只是统计了元素数量，所以 count-min sketch 是可以接受相加相减的。
Count-min Sketch 应用
考虑 k-Heavy hitter(k-HH) 问题：给定长度为 \(N\) 的在 \([n]\) 上的数组，求出现次数前 \(k\) 多的元素。这个问题的应用例如用来查找那些异常流量或者访问较多的页面。
近似 k-HH 问题：你需要找到所有出现至少 \(N/k\) 次的元素，并且你还可以返回其他元素，返回的其他元素出现不少于 \(N/k-\epsilon N\) 次。
基于 count-min 的方法做数据流上的近似 k-HH，直接使用 count-min sketch 来存每个元素出现次数就行了，每次新加一个元素就查一下出现次数看是否满足条件即可，你找到的所有元素数量大概率是不超过 \(k\) 的，所以直接用表记录这些元素即可，动态增加 \(N\) 也没有任何问题。
标签：le,复习,2023,算法,概率,哈希,delta,程序设计,mathrm From： https://www.cnblogs.com/lsq147/p/17488961.html