algorithm - 在不使用反馈的情况下查找数组中的偶数

Question

我看到这篇文章:Finding even numbers in an array我正在考虑如何在没有反馈的情况下做到这一点。这就是我的意思。

Given an array of length n containing at most e even numbers and a function isEven that returns true if the input is even and false otherwise, write a function that prints all the even numbers in the array using the fewest number of calls to isEven.

帖子上的答案是使用二进制搜索，这很简洁，因为它并不意味着数组必须按顺序排列。您必须检查数字是否为偶数的次数是 e log n 而不是 if n 因为您进行了二进制搜索 (log n ) 每次找到一个偶数 (e 次)。

但这个想法意味着您将数组分成两半，测试均匀性，然后根据结果决定保留哪一半。

我的问题是，你是否可以在一个固定的测试方案中击败 n 调用，在这个方案中，你可以在不知道结果的情况下检查所有你想要的数字是否均匀，然后找出偶数在哪里根据结果​​完成所有测试后。所以我猜它是无反馈或盲目或类似的术语。

我想了一会儿，想不出任何东西。二进制搜索的想法在这个约束下根本不起作用，但也许别的东西可以吗？即使减少到 n/2 调用而不是 n(是的，我知道它们是同一个 big-O)也会很好。

Answer 1

“无反馈或盲目”的技术术语是“非自适应”。 O(e log n) 调用仍然足够，但算法涉及更多。

我们不测试产品的均匀性，而是测试总和的均匀性。设 E ≠ F 是 {1, …, n} 的不同子集。如果我们有一个数组 x₁, …, x_n 在位置 E 和另一个数组 y₁, …, y_>n 位置F为偶数，{1, …, n}的子集J有多少个满足

(∑_{i in J} x_i) mod 2 ≠ (∑_{i in J} y_i)模式 2？

答案是 2^n-1。令 i 为满足 x_i mod 2 ≠ y_i mod 2 的索引。令 S 为 {1, …, i - 1, i + 1, … n}。 J = S 是一个解决方案或 J = S union {i} 是一个解决方案，但不是两者都是。

对于每个可能的结果 E，我们需要进行调用以消除所有其他可能的结果 F。假设我们随机进行 2e log n 次调用。对于每一对 E ≠ F，我们仍然无法区分 E 和 F 的概率是 (2^n-1/2ⁿ)^{2e log n} = n^-2e，因为有 2ⁿ 种可能的调用，只有 2^n-1 种无法区分。最多有 n^e + 1 个 E 选项，因此最多有 (n^e + 1)n^e/2 对。通过联合边界，存在一些不可区分的对的概率至多为 n^-2e(n^e + 1)n^e/2 < 1(假设我们正在研究一个有趣的情况，其中 e ≥ 1 且 n ≥ 2)，因此存在一个 2e log n 调用序列来完成这项工作。

请注意，虽然我使用随机性来表明存在良好的调用序列，但生成的算法是确定性的(当然，也是非自适应的，因为我们选择的序列没有结果的知识)。