下面，我们来看一个例子：一个总体S中含有10000个测试元，其中有100个测试元满足条件A，现在，若从S中取出100个测试元进行测试，则检查出S满足性质P的概率约为：63.6%，若取200个测试元，则检查出的概率为86.9%，若取300个，则检查出的概率可达95.3%。
下图中给出了取的个数与正确率之间的关系(注意：这里只画了取0至800个时的图像，当取800个以上时，由于其正确率太接近100%，其图像近似一条水平直线而没有再画出的意义)：
从图中还可以看出，只要抽样大约70个，就有50%的正确率，抽样大约230个，就有90%的正确率。
再看一个例子：如果总体S是{’A’,’B’, ,’Z’}的所有子集，而条件A是同时含有’A’~’G’的子集。按照上面，根据上面一例，可以想到，如果取一定量的子集测试，效果也会比较好，但好，对于总体S，它存在一些特殊的子集——如空集 、全集{’A’,’B’, ,’Z’}、只含一个元素的集合{’A’},{’B’} 这些都是我们认为比较特殊的集合，如果从这些特殊的集合中先取出几个测试，则可能在这些
国家集训队2005论文集
集合中就能找到满足条件A的，如此例中取全集显然就会满足条件。
下面看一个具体的实例：
例：Intuitionistic Logic(直觉主义逻辑)③ 题目大意
给定一个有向无环图G=(V,E)，在顶点V之间建立一些偏序关系：对于x,y V，定义x≤y当且仅当x到y之间存在路径(可能长度为0)。对于一个顶点集合S，定义Max(S)为S中所有最大元素的集合(即Max(S)中的任意一个顶点都不可能通过一条或多条E中的边到达S中的其他顶点)，写成表达式的形式为：
Max(S)={x S|不存在y S,x≠y,x≤y}
令β为所有满足Max(S)=S的集合所组成的集合，即： β={S|Max(S)=S}
令0=Max(V)，1= ，显然0和1都属于β 定义β中元素的一些操作： P=>Q={x Q|不存在y P,x≤y}, P Q=Max(P∪Q),
P Q=Max({x V|存在y P,z Q,x≤y,x≤z}),
P=(P=>0),
P≡Q=((P=>Q) (P=>Q))
问题：对于一个含有变量的表达式，问是否无论变量如何在β中取值，其运算结果都是1？
数据范围：其中|V|≤100；|E|≤5000；对于同一个图，要处理k个表示式，k≤20；每个表达式长度不超过254个字符；|β|≤100； Hj 106 (vj是在第j个表达式
v
1 j k
中用到的变量个数)
分析
本题的最后一个数据范围
1 j k
Hj 106其实暗示了我们，此题可以用枚举来
v
做，即枚举所有变量的所有可能取值。显然，如果要求完全正确，变量取值的总方案数是不可能减少的，即可能达到106，这时，就得设法减少计算的复杂度。显然，上面的基本运算都是O(|V|)或O(|E|)或更高的，而计算一个表达式可能要
③
题目来源：ACM ICPC 2002-2003, Northeastern European Region, Northern Subregion，原题请见附件。
国家集训队2005论文集
使用上百次基本运算，这样，尽管此题有5秒的时限，这样的枚举也是很难出解的。
由|β|≤100，可以想到，将β中的每一个元素先用一个整数代替，并计算出对这些数进行上面的基本运算所得的值(当然也用整数表示)。对这些值列一个表，以后计算时就只要从表中查找结果了。这样，基本运算的复杂度就可以降到O(1)，总的复杂度就可以降为O( Hj*|B|)。
v
1 j k
此题还有一种解决方法，那就是抽样。将变量取β中一些比较特殊的值(如0，1， )看作特殊样品，其它的看作一般样品。抽取一些特殊样品和一些一般样品，对它们进行测试，如果对于一个式子，所有的样品都满足条件，则说明式子满足条件，否则说式子满足条件。实践证明，只要抽取不到1000个样品即可得到比较高的正确率。
当然，对于这类多测试数据的题目，要基本保证一个测试点对，每组测试数据的正确概率必须更高一些。如：对于有20个组测试数据的测试点，如果保证每组数据的正确概率为95%，则整个测试点的正确概率只有0.9520，还不到36%；如果保证每组数据的正确概率为99%，整个测试点的正确概率才82%；如果每组数据正确概率达到99.9%，则整个测试点的正确概率就会有98%。
这里特别要说明的是：一般情况下，抽样的数目应该尽量多(在保证不超时的前提下)，这样才能保证正确概率较大。
抽样法的实际运用：
在测试质数时，抽样法是一个非常有用的工具。下面给出一种质数判定方法： 对于待判定的整数n。设n-1=d*2s(d是奇数)。对于给定的基底a，若
ad 1(modn) 或存在0≤r<s使
a
d*2r
1(modn)
则称n为以a为底的强伪质数(Strong Pseudoprime)。利用二分法，可以在O(log2n)的时间内判定n是否为以a为底的强伪质数。
对于合数c，以小于c的数为底，c至多有1/4的机会为强伪质数(Monier 1980, Rabin 1980)。
国家集训队2005论文集
根据这条，判断一个数n是否为质数，可以随机地抽取小于n的k个数为底。这样，正确的概率不小于1-4-k。显然，这已经非常优秀了，通常只要取几十组就可以保证基本正确。
如果不是随机抽样，而是抽样特殊情况——最小的几个质数，则：
④
如果只用2一个数进行测试，最小的强伪质数(反例)是2047(所以一个数显
然不够)；
如果用2和3两个数进行测试，最小的强伪质数大于106； 如果用2,3,5进行测试，最小的强伪质数大于2×107；
如果用2,3,5,7进行测试，最小的强伪质数大于3×109，已经比32位带符号整数的最大值(Pascal中的Maxlongint)还大了。
可见，通常只要抽取2,3,5,7这几个固定的数进行测试就能保证测试的正确性了。
我们知道，最朴素的质数测试方法是用2
n进行试除。这样，测试一个数的复杂度为O(n0.5)，用上面的方法，每次测试只要O(log2n)的复杂度，由于只要测试很少的几次，所以，其总复杂度仍是O(log2n)的。可见，用抽样的方法对质数进行测试的算法明显优于朴素的质数测试法。
小结
从上面的例子可以看出，由于抽样法只对总体中的一部分更行测试，所以它要测试的次数非常少，从而使得算法需要的时间比完全枚举少很多，算法的效率也会高很多。
1.3 部分忽略法
在信息学中，可能会遇到这样情况：一个题的分类非常复杂，且某些情况的处理非常复杂，但这些情况往往不是主要情况(即出现的概率很小或不处理这些情况对答案不会造成很大的影响)。有时，忽略这些复杂却影响不大的情况会使程序达到令人满意的结果。