1、 计算机科学中非完美的例子计算机科学中非完美的例子 图片、音频、视频的压缩图片、音频、视频的压缩 很多压缩率比较高的压缩方法都是有损压缩很多压缩率比较高的压缩方法都是有损压缩 密码验证密码验证 很多都是多对一，通过验证的不一定是正确的很多都是多对一，通过验证的不一定是正确的 搜索引擎搜索引擎 不一定能搜索到所有匹配的内容不一定能搜索到所有匹配的内容较小的磁盘空间较小的磁盘空间安全、实用安全、实用方便、快捷方便、快捷非完美算法非完美算法 在信息学乃至整个计算机科学领域，不一定在信息学乃至整个计算机科学领域，不一定绝对正确的算法就是最好的算法，有可能一绝对正确的算法就是最好的算法，有可能一个在绝大
2、多数情况下正确的算法个在绝大多数情况下正确的算法(非完美算法非完美算法)比一个完全正确的算法更有前途。比一个完全正确的算法更有前途。时间使用较少时间使用较少 空间使用较少空间使用较少 实现较容易实现较容易 容易被接受容易被接受 非完美算法的一些常见方法非完美算法的一些常见方法 随机贪心随机贪心 抽样测试抽样测试 部分忽略部分忽略 周咏基周咏基论随机化算法的论随机化算法的原理与设计原理与设计(*)(*)抽样测试法抽样测试法 抽样：从统计总体中，任意抽出一部分单位抽样：从统计总体中，任意抽出一部分单位作为样本，并以其结果推算总体的相应指标。作为样本，并以其结果推算总体的相应指标。抽样测试法抽样测试
3、法s满足条件满足条件A具有性质具有性质P抽样测试法抽样测试法10000个元素个元素100个满足条件个满足条件只要少量抽样就能取只要少量抽样就能取 得较高的正确率得较高的正确率抽样测试法抽样测试法 在抽样测试时，有时总体中存在一些特殊的在抽样测试时，有时总体中存在一些特殊的元素，这些元素满足条件的概率往往与其他元素，这些元素满足条件的概率往往与其他元素满足条件的概率相差较大。如果特别的元素满足条件的概率相差较大。如果特别的在这些元素中抽取一些进行测试，则可以加在这些元素中抽取一些进行测试，则可以加快出解的速度或增大解的正确率。快出解的速度或增大解的正确率。特殊抽样特殊抽样抽样测试法抽样测试法特殊
4、抽样特殊抽样=A,B,C,Z总体：总体：的所有子集的所有子集条件：含条件：含A,B,C,G的集合的集合取特殊元素取特殊元素即满足条件！即满足条件！质数判定质数判定 朴素的质数判定方法：朴素的质数判定方法：用用2试除。试除。O(n0.5)抽样测试法：抽样测试法：在在2中抽取中抽取k个试除。个试除。nnStrong Pseudoprime 对于奇数对于奇数n和正整数和正整数a，设，设n-1=d2s(d为奇数为奇数)，若：若：ad1(mod n)或或 存在存在0rs，使，使-1(mod n)则称则称n是以是以a为底的为底的强伪质数强伪质数(Strong Pseudoprime)。判断：判断：O(lo
5、g2n)rda2质数测试质数测试 当当a不是不是n的整数倍时，质数的整数倍时，质数n必然是以必然是以a为底为底的强伪质数。的强伪质数。在所有可能的在所有可能的a中，一个合数至多有的机会中，一个合数至多有的机会为强伪质数。为强伪质数。抽样测试：随机抽取抽样测试：随机抽取k个不同的个不同的a进行测试。进行测试。正确率大于正确率大于14k 时间复杂度为时间复杂度为O(klog2n)。14抽样测试抽样测试质数测试质数测试抽样测试抽样测试 特殊抽样：让特殊抽样：让a取最小的若干个质数。取最小的若干个质数。只用只用2测试：最小的强伪质数为测试：最小的强伪质数为2047，在小于，在小于2.51010中有中有
6、4842个强伪质数。个强伪质数。只用只用2,3测试：最小强伪质数大于测试：最小强伪质数大于1.3106。只用只用2,3,5测试：最小强伪质数大于测试：最小强伪质数大于2.5107。只用只用2,3,5,7测试：最小强伪质数大于测试：最小强伪质数大于3.2109。质数测试质数测试抽样测试抽样测试 一般情况下，只要用一般情况下，只要用2,3,5,7进行测试就能正进行测试就能正确的判断一个数是否为质数。确的判断一个数是否为质数。时间复杂度：时间复杂度：O(log2n)抽样测试法抽样测试法明显降低时间复杂度！明显降低时间复杂度！抽样测试法抽样测试法部分忽略法部分忽略法 在信息学中，可能会遇到这样情况：一
7、个题在信息学中，可能会遇到这样情况：一个题的分类非常多，同时某些情况的处理非常复的分类非常多，同时某些情况的处理非常复杂，但这些情况往往不是主要情况杂，但这些情况往往不是主要情况(即出现的即出现的概率很小或不处理这些情况对答案不会造成概率很小或不处理这些情况对答案不会造成很大的影响很大的影响)。有时，忽略这些复杂却对结果。有时，忽略这些复杂却对结果影响不大的情况仍然可以达到令人满意的结影响不大的情况仍然可以达到令人满意的结果。果。部分忽略法部分忽略法ProblemABD30%40%正确率：正确率：99%99%C29%1%少少多多少少非常多非常多情况情况 出现率出现率 处理用时处理用时判断点是否
8、在多边形内判断点是否在多边形内 给出一个点和一个简单多边形给出一个点和一个简单多边形(设点不在多边设点不在多边形的边上形的边上)，判断点是否在多边形内。，判断点是否在多边形内。方法：方法：判断点是否在多边形内判断点是否在多边形内 特殊情况：特殊情况：忽略特殊情况忽略特殊情况！？ABCD判断点是否在多边形内判断点是否在多边形内 射线经过多边形的顶点是一种非常特殊的情射线经过多边形的顶点是一种非常特殊的情况。况。而我们取的是一条非常特殊的射线而我们取的是一条非常特殊的射线与与x轴轴平行的射线。平行的射线。经验表明，特殊的射线经过多边形的顶点的经验表明，特殊的射线经过多边形的顶点的几率会大于一般的射
9、线！几率会大于一般的射线！解决方法：解决方法：取一条一般的射线！取一条一般的射线！判断点是否在多边形内判断点是否在多边形内ABCD判断点是否在多边形内判断点是否在多边形内多取几条！多取几条！将出现次数最多的结果作为将出现次数最多的结果作为正确结果正确结果设取一条射线，其经过多边形设取一条射线，其经过多边形顶点的概率为顶点的概率为x，取，取n条，所得条，所得结果的正确率不小于结果的正确率不小于1-xn/2部分忽略部分忽略 部分忽略法能减轻我们的思维负担和编程复部分忽略法能减轻我们的思维负担和编程复杂性。杂性。部分忽略法通常要加入一些小小的技巧。使部分忽略法通常要加入一些小小的技巧。使被忽略的情况
10、对结果影响尽量小！被忽略的情况对结果影响尽量小！非完美算法非完美算法 共同点：共同点：不完全性不完全性 优点优点 时空消耗低时空消耗低 编程复杂度低编程复杂度低 思维复杂度低思维复杂度低 能减少编程错误能减少编程错误 缺点缺点 不完全正确不完全正确总结总结 在信息学竞赛以及实际应用中，并不是完全在信息学竞赛以及实际应用中，并不是完全正确的算法就一定比非完美的算法表现得好，正确的算法就一定比非完美的算法表现得好，因为非完美算法的不完全性，反而使非完美因为非完美算法的不完全性，反而使非完美算法在一些方面比正确算法表现得更好。因算法在一些方面比正确算法表现得更好。因此，此，合理的使用合理的使用非完美
11、算法能取得非常令人非完美算法能取得非常令人满意的结果。满意的结果。忠告忠告 在能用完全正确的算法时要尽量使用完全正在能用完全正确的算法时要尽量使用完全正确的算法，只有当确实难想到很好的方法或确的算法，只有当确实难想到很好的方法或时间比较紧时才使用非完美算法。时间比较紧时才使用非完美算法。结束语结束语 想了解更多，欢迎阅读我的论文。里面还有想了解更多，欢迎阅读我的论文。里面还有一些更好玩的例子，如：一些更好玩的例子，如：NOIP2003的的传染传染病控制病控制、ACM的的直觉主义逻辑直觉主义逻辑以及以及IOI2004的的Polygon。RPRP类问题类问题 对于一个判定类问题，如果存在一个随机算
12、法，当对于一个判定类问题，如果存在一个随机算法，当此算法判定结果为否时，原问题的结果必为否，同此算法判定结果为否时，原问题的结果必为否，同时，当此算法的判定结果为是时，原问题的结果为时，当此算法的判定结果为是时，原问题的结果为是的概率大于是的概率大于50%，那么这个问题属于，那么这个问题属于RP类问题类问题。该算法称为该算法称为Monte-Carlo算法算法。如果一个问题是如果一个问题是RP类问题，可以通过多次运行它的类问题，可以通过多次运行它的一个一个Monte-Carlo算法而得到算法而得到“几乎每次都是正确几乎每次都是正确”的算法。的算法。与与Monte-CarloMonte-Carlo算法算法
