非确定性算法Non-deterministic algorithms _算法

非确定算法：随机与近似确定性算法
对于给定的输入，算法的输出和运行时间不变
非确定性算法Non-
对于给定的输入，算法的输出或运行时间是不确定的
近似算法随机算法随机算法随机算法的优势实现简单；更加高效；避开最坏情况（防hack）；常见的随机算法关于随机和概率的一个问题
在半径为
的圆上取一弦，弦长大于
的概率是多少？
引例：快速排序（确定性算法）随机化快速排序期望时间复杂度为O(n log n)对谁的期望？关键在于：数据与算法之间的博弈对算法分布求期望（√）vs对数据分布求期望（×）在算法分布上，对任一数据求期望（为什么O(n log n)）两个疑问错误的-Yates算法？对i+1到n换；对1到n换为什么洗牌后，每次指定位置元素等价于每次在随机位置选元素？随机化快速排序时间复杂度分析注意共有n！个算法，每个算法比较次数可模拟算出如n=10的
分布：若n更大，如何估计
？采样！随机化快速排序时间复杂度分析令
为数组
中第

文章插图
大元素，定义如下指示器随机变量于是，随机变量
（即算法的比较次数）满足因此，根据期望的线性性质有
是多少？思考物理意义！（回顾弦问题）事件什么时候发生？随机化快速排序时间复杂度分析
等概率取得的一个洗牌结果中，
和
【非确定性算法Non-deterministic algorithms】发生过比较的概率是？
随机化快速排序时间复杂度分析
：
对样本空间进行巧妙划分后，利用期望的线性性质可以解很多问题。由此，可以体会到用指示器随机变量的根本原因为：
随机算法引例：最小割Min cut
在连通无向图
上，至少删几条边可使原图不连通？
确定性算法关于问题的思考（最优&可行）
能否给出最小割的上界？可行解里较优的？（最小度数点）
最小割的随机算法（'s ）收缩操作：以均匀分布随机选择图的一条边，将边上两个点缩为一个点，并将两点间的所有边删除重复步骤1，知道图只剩下两个点（注意此时的图不再是简单图）最终，两点间的个数即为最小割简单分析失败案例
成功案例
算法分析
有多大概率，该算法可以给出一个正确的最小割呢？
假设图中有n个点，最小割为k 。此时即使最小割有多解，我们只关注其中一种，并用边集C表示（即C包含k条边）。于是，问题转为求在n-2次收缩操作中，均为选中C中边的概率。
在第一次的基础上，第二次收缩为于是在第i次收缩时由条件概率公式可得n-2次都为选C中边的概率为从未选中C中边的概率大于
，即算法成功率大于
此时如果拖过重复执行
次算法，全部失败的概率为换言之，在O(n^3)时间内，以超过
的概率找到最小割当重复足够多次后，找不到最小割的概率将会是无穷小随机算法两类随机算法
注意所有的随机性与数据无关
拉斯维加斯算法Las Vegas ：随机化快速排序蒙特卡罗算法Monte Carlo ：最小割随机算法两类随机算法之间的转化拉斯维加斯算法?蒙塔卡罗算法蒙塔卡罗算法?拉斯维加斯算法