『笔记』随机化算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了『笔记』随机化算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2613字，纯文字阅读大概需要4分钟。
内容图文
引言：长久的关系不会是道德式的自我感动 ??
一、时间期望值的估计
题目：假设\(1.. n\) 中每个数被选的概率相等，并且假设第 \(k\) 个数总是
出现在划分后两个数组中较大的数组 ，算法的期望时间为:
因为具有对称性，所以可以合并为
\[T(n)\le\frac{2}{n}\sum^{n-1}_{i=\frac{n}{2}}T(i)+O(n) \]二、\(n\) 皇后问题的随机算法
前 \(k\) 个 用\(BoolQueen\)随机放置皇后
\(n-k\) 个皇后用搜索回溯的方法进行放置，增加算法的正确性
对于不同的 \(k\) 值，假设 \(p\) 为算法成功的概率， \(s\) 为一次成功搜索访问的节点数的平均值，\(e\) 为一次不成功搜索访问的节点数的平均值，\(t\) 为算法找到一个解得平均时间
\[t=p\times s+(1-p)\times (e+t) \]\[t=s+e\times \frac{1-p}{p} \]可以发现，当全部用确定性算法的时候\((k=0)\) 争取性是\(100\)%的,但当全部用随机算法，虽然时间会减少大部分，但是正确性会大大降低，通过分析公式发现，当\(k=\frac{n}{2}\)左右时，正确性和时间都是较为理想的。
三、主元素测试问题
问题：
主元素：出现次数超过一半以上的元素
输入：\(n\) 个元素的数组 \(T\)
输出：如果存在主元素则输出\(“true”\)，否则\(“false”\)
算法 \(Majority(T,n)\)
-
\(i\) =Random(1,n)
-
\(x\) =T(i)
-
计数 \(x\) 在 \(T\) 中出现的个数 \(k\)
-
if \(k>n/2\) then return true
-
else return false
如果回答\(true\),那么 \(T\) 中存在主元素，算法正确，如果回答 \(false\),\(T\)仍然可能会存在主元素，算法可能会出错，回答正确概率大于\(\frac{1}{2}\)
算法 \(BoolMajority(T,n)\)
-
if \(Majority(T,n)\) then return true
-
else return \(Majority(T,n)\)
\(BoolMaiority\) 的算法正确概率
\[p+(1-p)p+(1-p)^2p=1-(1-p)^2>\frac{3}{4} \]调用 \(k\) 次的正确概率为\(1-(1-p)^k>1-2^{-k}\)
四、串相等测试（随机化字符串哈希）
问题：\(A\) 有一个长串 \(x\), \(B\) 有长串 \(y\)，\(A\) 和 \(B\) 希望知道 \(x=y\)?
方法一：正常用哈希匹配，占用空间大
方法二：传递子串进行比较，正确性不确定
\(A\) 用 \(x\) 导出一个短串 \(f(x)\) \((fingerprints)\)
\(A\) 将 \(f(x)\) 发送到 \(B\)
\(B\) 使用同样方法导出相对于 \(y\) 的短串 \(f(y)\)
\(B\) 比较 \(f(x)\) 与 \(f(y)\)
如果 \(f(x)\neq f(y)\)则 \(x \neq y\);
如果 \(f(x) = f(y)\)，则不确定.
\(Trick\)
设 \(x\) 和 \(y\) 的二进制表示为正整数 \(I(x)\), \(I(y)\)
选择素数 \(p\), 指纹函数为
\(I_p(x) = I(x)\ \ mod \ \ p\)
\(A\) 传送 \(p\) 和 \(I_p(x)\) 给 \(B\). 当 \(p\) 不太大时，传送一个短串.
存在问题：
\(x = y \to I_p(x) = I_p(y)\)
\(Ip(x) = Ip(y) ? x = y\)
出错条件：固定
\(p | (I(x) - I(y))\)
改进版 \(Trick\)
改进方法： 随机选择素数 p 进行测试
算法 \(StringEqualityTest\)
-
随机选择小于 \(M\) 的素数 \(p\) //M为正整数
-
\(A\) 发送 \(p\) 和 \(I_p(x)\) 给 \(B\)
-
\(B\) 测试是否 \(I_p(x) = I_p(y)\)
出错的必要条件：
\(x\) 的位数等于 \(y\) 的位数
\(p | (I(x)-I(y))\)
该笔记因快速幂终结!
内容总结
以上是互联网集市为您收集整理的『笔记』随机化算法全部内容，希望文章能够帮你解决『笔记』随机化算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。