Dan*_*iel 7 algorithm binary-search
我看到这篇文章:在数组中查找偶数数字,我在考虑如何在没有反馈的情况下完成它.这就是我的意思.
给定一个长度为n的数组,其中包含最多
e偶数和一个函数isEven,如果输入为偶数则返回true,否则为false,编写一个函数,使用最少的调用次数打印数组中的所有偶数isEven.
帖子上的答案是使用二进制搜索,这是很整洁的,因为它并不意味着数组必须按顺序排列.的次数,你必须检查是否有数字为偶数的e log n,而是如果n因为你做一个二进制搜索(log n)找到一个甚至每一时间(数e倍).
但是这个想法意味着你将数组分成两半,测试均匀度,然后根据结果决定保留哪一半.
我的问题是你是否可以n在一个固定的测试方案上打电话,你可以在不知道结果的情况下检查你想要的所有数字,然后在你完成所有测试之后找出偶数的位置.结果.所以我猜这不是反馈或盲目或类似的术语.
我有一段时间在思考这个问题并且无法想出任何东西.二元搜索的想法在这个约束下根本不起作用,但也许其他的东西呢？即使是n/2打电话而不是n(是的,我知道他们是同一个大O)也会很好.
小智 7
"无反馈或盲目"的技术术语是"非适应性".O(e log n)调用仍然足够,但算法更加复杂.
我们不是测试产品的均匀度,而是测试总和的均匀度.设E≠F是{1,...,n}的不同子集.如果我们有一个数组x 1,...,x n在位置E处具有偶数,而另一个数组y 1,...,y n在位置F处具有偶数,则{1,...,n}的子集J满足多少
(Σiin J x i)mod 2≠(Σiin J y i)mod 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 n)2e log n = n -2e,因为有2 n个可能的呼叫且只有2 n-1个未能区分.E 最多有n e + 1个选择,因此最多(n e + 1)n e/2对.通过联合约束,存在一些不可区分对的概率最多为n -2e(n e + 1)n e/2 <1(假设我们正在研究e≥1且n≥2的有趣情况) ,所以存在一系列2e log n调用来完成这项工作.
请注意,虽然我使用随机性来表明存在良好的调用序列,但结果算法是确定性的(当然,非自适应,因为我们在不知道结果的情况下选择了该序列).
您可以使用中国剩余定理来做到这一点。我要稍微改变一下你的符号。
假设您的N数字最多为E偶数。选择一系列不同的质数幂q1,q2,...,qk，使得它们的乘积至少为N^E，即
qi = pi^ei
其中pi是素数ei > 0是整数并且
q1 * q2 * ... * qk >= N^E
现在制作一堆0-1矩阵。令Mi为矩阵，其中行和列qi x N中的条目具有if和else。例如，如果，则行在列和其他地方都有 1。rc1c = r mod qi0qi = 3^222, 11, 20, ... 2 + 9j0
现在将这些矩阵垂直堆叠得到一个Q x N矩阵M，其中Q = q1 + q2 + ... + qk。的行M告诉您哪些数字相乘（非零位置）。Q这给出了您需要测试均匀度的产品总数。j将每一行称为“试验”，如果j该行的第 th 列非空，则称“试验涉及”。您需要的定理如下：
j定理：当且仅当所有涉及的试验都是偶数时，位置上的数字才是j偶数。
因此，您进行了总共的Q试验，然后查看结果。如果您明智地选择素数幂，那么Q应该明显小于N。渐近结果表明您总是可以得到Q以下顺序
(2E log N)^2 / 2log(2E log N)
这个定理实际上是中国剩余定理的推论。我见过的唯一使用这种方法的地方是组合组测试。显然，这个问题最初是在对二战归来的士兵进行梅毒检测时出现的。