1.对N个芯片,在保证好芯片比坏芯片多的情况下,取出一块芯片(为叙述方便,设为芯片X),与其他所有芯片做测试,记录相互间的结果.
2.按照芯片X对其他芯片的结果,将其他芯片分成两组:GOOD组和BAD组.
3.如果GOOD组的数目<BAD的数目,则X为坏芯片,跳到5.
4. 如果GOOD组的数目>=BAD组的数目,并且GOOD组对X的测试为good(认为X好芯片),则X确实是好芯片,算法结束(因为在N-1中,至少半数的芯片认为X为不是坏芯片,考虑到好芯片比坏芯片多,可归谬证明);否则,只要有一个GOOD组芯片对X的测试为bad,则X为坏芯片,继续.
5.X为坏芯片,故去除X,将所有芯片分成两组:对X的测试为bad的保留,对X的测试为good的去除.考虑到所有的好芯片都保留了(它们对X的测试必为bad),所以仍然满足好芯片比坏芯片多的条件.跳到1,继续.
以上算法保证可以结束.因为如果测试出X是坏的,那么每次N至少减一.并且,因为好芯片比坏芯片多,算法必定是在第4步结束.而不会出现芯片降到1的情况(只要初始的芯片数>=2)
题目中,初始N=2k.其复杂度在最坏的情况下测试次数(假设一次测试同时出现相互的结果,否则次数*2)为: k + (k+1) + ... + (2k-1) = 1/2 * k(3k-1) = O(k^2)