0
    Finding ONE good VLSI chip in a population of good and bad ones, by using the
 pair test.      
        Chip A      Chip B      Conclusion  
        -------     -------     ----------  
        B is good   A is good  both are good or both are bad  
        B is good   A is bad    at least one is bad  
        B is bad    A is good   at least one is bad  
        B is bad    A is bad    at least one is bad  


    Assumption : number of goods > number of bads
    We can solve this in O(n) time complexity by splitting the population in half 
    every time and collecting one element of the GOOD, GOOD pair. 
     T(n) = T(n/2) + n/2
    But to collect the pairs we need n/2 memory separately. 
    Can we do this in-place without using extra memory ?? 
4

1 回答 1

0

该算法基于“我们可以移除这个芯片吗?”这个问题。因此,对于要删除的每个芯片,我们只需将其从链表中删除,就位(或者更确切地说,根本没有位置)。

于 2012-06-05T22:22:08.880 回答