从一组n个球中找出缺陷球

Question

类似于缺陷球问题，给你n个球，但是有一个数目未知的缺陷球和好球。至少有一个好球和至少一个有缺陷的球。所有好球的重量都一样，所有有缺陷的球都是一样的，但是好球的重量比有缺陷的球轻，如果有平衡的话，把有缺陷的球和好的球分开。

我对解决方案的天真尝试就是将第一个球放在一个列表中，然后遍历整个列表，并相应地将它们放在各自的列表中。然而，这显然是一个O(n)解。我想知道是否还有更有效的方法？

Answer 1

在最坏的情况下，你找不到比O(n)加权更好的解。有2^n种可能的结果(2^n种给每个球分配“好”或“坏”的方法)。每种称量都有三种可能的结果，因此m加权可以区分3^m可能的结果。

因此，要区分所有2^n可能的结果，至少需要log3(2^n)加权，它等于n*log3 3(2)= O(n)。

因此，在最坏的情况下，最简单的解(取一个球并将其与另一个球进行权衡)是最好的解。

注意:这个证明是基于与比较排序不能比O(n*logn)更好的证明的相同的观点。