引言:长久的关系不会是道德式的自我感动
一、时间期望值的估计
题目:假设(1.. n) 中每个数被选的概率相等,并且假设第 (k) 个数总是
出现在划分后两个数组中较大的数组 ,算法的期望时间为:
因为具有对称性,所以可以合并为
二、(n) 皇后问题的随机算法
前 (k) 个 用(BoolQueen)随机放置皇后
(n-k) 个皇后用搜索回溯的方法进行放置,增加算法的正确性
对于不同的 (k) 值,假设 (p) 为算法成功的概率, (s) 为一次成功搜索访问的节点数的平均值,(e) 为一次不成功搜索访问的节点数的平均值,(t) 为算法找到一个解得平均时间
可以发现,当全部用确定性算法的时候((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) 的算法正确概率
调用 (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) eq f(y))则 (x eq 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 o 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)))
该笔记因快速幂终结!