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

Question

与有缺陷的球问题类似，您可以获得n个球，但有不明数量的缺陷球和良好的球。至少有1个好球和至少1个有缺陷的球。所有好的球的重量都是相同的，所有有缺陷的球的重量都是相同的，但好球的重量要小于有缺陷的球，并且给出平衡后，将有缺陷的球与好的球分开。

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

Answer 1

在最糟糕的情况下，您找不到比O（n）称重更好的解决方案。有2^n个可能的结果（2^n种方式为每个球分配“好”或“坏”）。每种称量有三种可能的结果，因此称量可以区分3^m可能的结果。因此，要区分所有2^n个可能的结果，至少需要log3（2^n）称量，这等于n * log3（2）= O（n）。

因此，在最坏的情况下，最简单的解决方案（拿一个球并对其他每个球进行权衡）是最好的解决方案。

注意：此证明基于与比较排序不能渐近地好于O（n * logn）的证明相同的想法。