algorithm - 解决是非测试

Question

有一个包含 N 个 YES 或 NO 问题的测试。你可以写测试，教授会告诉你有多少答案是正确的。通过考试最快的方法是什么？ IE。以最少的试验次数正确回答所有问题。

UPD N+1 试验的解决方案很明显。在每次试验中，我们都会对一个问题给出正确答案。它是 1 比特的信息。但是教授每次给我们一个从0到N的数字，就是log₂(N + 1)位信息。这就是为什么最好的解决方案具有 O(N/log(N)) 的复杂性。 我正在寻找具有次线性最差时间复杂度的任何解决方案。

Answer 1

相对于N+1方案的明显改进:

从所有 Y 的答案开始。

然后我们确切地知道有多少是/否。

令 p 为在任何给定位置上获得"is"的概率。 p >= 1/2 不失一般性。

然后我将平均尝试 2 - p^2 次来揭示两个第一个答案。

我更改了前两个问题的答案。 至少 p^2 的时候我会知道他们两个的确切答案。如果不是 - 那么我至少知道其中一个是 Y，另一个是 N，我需要再问一个问题。

所以在 p = 1/2 的最坏情况下，我需要 1 + N * 7/8。