随机算法|集2（分类和应用）

我们强烈建议将下面的帖子作为这篇文章的先决条件。

随机算法|集1（介绍和分析）

分类

随机算法分为两类。

拉斯维加斯： 这些算法总是产生正确或最佳的结果。这些算法的时间复杂度基于一个随机值，时间复杂度被评估为期望值。例如，随机快速排序总是对输入数组进行排序，然后 快速排序的预期最坏情况时间复杂度为O（nLogn） .

蒙特卡洛： 以一定的概率产生正确或最佳的结果。这些算法具有确定的运行时间，通常更容易找出最坏情况下的时间复杂度。例如 Karger算法的实现 产生概率大于或等于1/n的最小切割 ² （n是顶点数），最坏情况下的时间复杂度为O（E）。另一个例子是 费米特素性检验法 .

理解分类的示例：

Consider a binary array where exactly half elements are 0
and half are 1. The task is to find index of any 1.  

这项任务的拉斯维加斯算法是不断挑选一个随机元素，直到我们找到一个1。同样的蒙特卡罗算法是不断地选取一个随机元素，直到我们找到1或者我们尝试了最大允许次数，比如k。 拉斯维加斯算法总是找到1的索引，但时间复杂度被确定为期望值。这个 成功前的预期试验次数 为2，因此预期时间复杂度为O（1）。 蒙特卡罗算法发现概率为[1–（1/2）的1 ^K ]蒙特卡罗的时间复杂度是O（k），这是确定性的

应用和范围：

• 考虑一个基本上进行排序的工具。让这个工具被许多用户使用，很少有用户总是使用这个工具来处理已经排序好的数组。如果该工具使用简单（非随机）快速排序，那么这几个用户将永远面临最糟糕的情况。另一方面，如果工具使用随机快速排序，则没有用户总是遇到最坏的情况。每个人都得到了预期的O（n logn）时间。
• 随机算法在密码学中有着巨大的应用。
• 负载平衡 .
• 数论应用： 素性检验
• 数据结构：哈希、排序、搜索、， 订单统计 和计算几何。
• 代数恒等式：多项式与代数恒等式 矩阵身份验证 .交互式证明系统。
• 数学规划：更快的线性规划算法，将线性规划解舍入为整数规划解
• 图算法：最小生成树，最短路径， 最小切割 .
• 计数和枚举：矩阵永久计数组合结构。
• 并行和分布式计算：避免死锁分布式共识。
• 概率存在性证明：证明一个组合对象在一个合适的概率空间中以非零概率出现。
• 去随机化：首先设计一个随机算法，然后论证它可以去随机化以产生确定性算法。

资料来源： http://theory.stanford.edu/people/pragh/amstalk.pdf https://en.wikipedia.org/wiki/Randomized_algorithm

本文由 阿什什·夏尔马 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论