CLSR 칩 테스트 문제

Question

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 ?? 

Answer 1

알고리즘은 "이 칩을 제거 할 수 있습니까?"라는 질문을 기반으로합니다. 따라서 각 칩을 제거하려면 링크 된 목록에서 해당 칩을 지우는 것만으로 간단하게 지울 수 있습니다.