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

Question

与有缺陷的球问题类似，您有 n 个球，但有未知数量的有缺陷的球和好球。至少有 1 个好球和至少 1 个有缺陷的球。所有好球的重量都相同，所有有缺陷的球的重量都相同，但好球的重量比有缺陷的球轻，并且在平衡的情况下，将有缺陷的球与好的球分开。

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

Answer 1

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

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

因此，在最坏的情况下，平凡的解决方案(取一个球并将其与其他每个球权衡)是渐进的最佳解决方案。

注意:这个证明基于与比较排序不能渐近优于 O(n*logn) 的证明相同的思想。