文档介绍：长郡中学胡伟栋
计算机科学中非完美的例子
图片、音频、视频的压缩
很多压缩率比较高的压缩方法都是有损压缩
密码验证
很多都是多对一,通过验证的不一定是正确的
搜索引擎
不一定能搜索到所有匹配的内容
较小的磁盘空间
安全、实用
方便、快捷
非完美算法
在信息学乃至整个计算机科学领域,不一定绝对正确的算法就是最好的算法,有可能一个在绝大多数情况下正确的算法(非完美算法)比一个完全正确的算法更有前途。
时间使用较少
空间使用较少
实现较容易
容易被接受
非完美算法的一些常见方法
随机贪心
抽样测试
部分忽略
……
——周咏基《论随机化算法的
原理与设计》
(*)
(*)
抽样测试法
抽样:从统计总体中,任意抽出一部分单位作为样本,并以其结果推算总体的相应指标。
抽样测试法
s
满足条件A
具有性质P
√
抽样测试法
10000个元素
100个满足条件
只要少量抽样就能取
得较高的正确率
抽样测试法
在抽样测试时,有时总体中存在一些特殊的元素,这些元素满足条件的概率往往与其他元素满足条件的概率相差较大。如果特别的在这些元素中抽取一些进行测试,则可以加快出解的速度或增大解的正确率。
——特殊抽样
抽样测试法——特殊抽样
α={‘A’,’B’,’C’,……,’Z’}
总体:α的所有子集
条件:含{‘A’,’B’,’C’,……,’G’}的集合
取特殊元素α即满足条件!
质数判定
朴素的质数判定方法:
用2~ 试除。O()
抽样测试法:
在2~ 中抽取k个试除。
×