CLSR芯片测试问题
CLSR芯片测试问题
提问于 2011-09-03 02:25:53
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 ?? 回答 1
Stack Overflow用户
发布于 2012-06-06 06:22:09
这个算法是基于这样一个问题：“我们能移除这个芯片吗？”因此，对于每个要移除的芯片，我们只需将其从我们的链表中删除，在适当的位置(或者更确切地说，没有任何位置)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7287743
复制相关文章
相似问题
腾讯云开发者
