用于确定N个输入中的X是否为真的最有效算法

Question

这个问题的灵感来自于我昨天的工作.

假设我们有N个输入,评估为真或假,哪种输入的X是真的最有效的方法是什么？

注意事项:

1. 输入不在数组中,因此如果将它们转换为数组,请考虑任何管理费用.
2. "效率最高"我指的是最佳平均情况(尽管我也希望看到最佳和最差情况统计数据).

---

这是我昨天遇到的两种方法.

1)将变量视为电路的布尔输入,并使用K-map减少它们

起初我认为这将是最有效的手段,因为它遵循电路逻辑,但我肯定有第二个想法.随着输入数量的增加,比较次数呈指数增长

2 inputs:
   1 of 2: if(1 OR 2)
   2 of 2: if(1 AND 2)

3 inputs:
   1 of 3: if(1 OR 2 OR 3)
   2 of 3: if((1 AND 2) OR (1 AND 3) OR (2 AND 3))
   3 of 3: if(1 AND 2 AND 3)

4 inputs:
   1 of 4: if(1 OR 2 OR 3 OR 4)
   2 of 4: if((1 AND 2) OR (1 AND 3) OR (1 AND 4) OR (2 AND 3) OR (2 AND 4) OR (3 AND 4))
   3 of 4: if((1 AND 2 AND 3) OR (1 AND 2 AND 4) OR (1 AND 3 AND 4) OR (2 AND 3 AND 4))
   4 of 4: if(1 AND 2 AND 3 AND 4)

... etc. ...

最好的情况是罚款(O(1)),但最坏的情况远比...差.

2)计数器和顺序if语句

这O(n)总是及时执行,这是可以的,但我希望有一个更好的最佳案例.

counter = 0

if(input 1)
   counter++

if(input 2)
   counter++

if(input 3)
   counter++

... etc. ...

if(counter >= X)
   // true

---

什么是比其中任何一个更有效的解决方案？

Answer 1

关于问题的复杂性
由于要求精确计数(而不是询问是否至少有 x个输入),问题非常清楚O(n):

• 一个人需要访问每一个输入,并且,
• 每个输入的工作独立于n(而给定输入的工作可能会根据输入的特定值而变化,如果输入的数量发生变化,[此输入]的工作量不会发生变化.)

我们当然可以实现次优算法,例如,在处理每个输入时[不必要地]访问所有其他输入,使其成为O(n ^ 2)实现,但这当然是愚蠢的.

这被断言,问题可能是关于......
使得实现更快的技巧
应该注意的是,尽管可能存在这样的技巧,但算法/问题的复杂性仍然固执地存在于O(n).

技巧1:更好的输入存储
不幸的是,问题表明输入来自命名变量,并且为了评估输入,必须考虑输入的任何转换成本[为了允许更快的计数].算法的整体性能.虽然这最终取决于底层语言,运行时等,但考虑到转换成本的需要很可能谴责任何基于备用存储的算法比保持输入原样的解决方案要慢.

技巧2:评估
的短路想法是false尽快(或不久之后)返回

• 打开的输入的运行计数大于X的数字(或者,如果我们计算关闭的输入数量,当此计数超过(n - X)时)
• 剩下要测试的输入数加上打开的输入的运行计数小于X.(或者在计算关闭输入的情况下类似的东西).

这个技巧相对简单,但计算早期退出测试所需值的额外成本可能会抵消[静态]早期退出所带来的收益.

技巧3:使用反向逻辑:计算关闭而不是打开的输入数量.(或统计两者).
这种方法的成本/收益取决于要测试的输入数量(问题的X)和我们可能对输入的统计先验(在给定时间相对均匀的输入数量)分散或者我们倾向于只有少量输入(或关闭)).

Chris Acheson提出的解决方案为Trick 2和Trick 3的使用提供了一个基线.假设我们可以对输入状态的分布做出一些假设,那么这个基线的额外性能改进将被驱动为"先验" :在计算输入本身之前完成的一些快速启发式方法将确定我们应该计算哪个状态(开或关或两者),哪个限制我们应该测试等等并分支到算法的相应"版本".

如果我们知道给定输入的开启或关闭的个别概率,那么额外的增益也是可能的,因为我们首先测试最多(或最少)可能的输入,以快速达到我们的"短路值".

关于这些优化算法的最佳情况/更糟糕的"复杂性"
假设

• 在给定时间打开的输入数量是均匀分布的
• 所有输入在给定时间内都有50%的变化
• X在1和n之间随机选择

技巧#2和#3的组合可能是O(X/2)平均的(我需要做数学,但这似乎是正确的).但是我觉得number of operations用X和/或n相对而言更明智,而不是滥用O符号...
假设所有操作大致产生相同的成本

• 初始化计数器或变量
• 测试输入或变量
• 加法或减法
• 等等

计算给定算法完成所需操作的总数,并因此使用此类计数,对于各种最佳/更差/平均情况来帮助确定特定算法更容易也更准确.
为了说明这一点,一个简单的实现只是系统地计算所有on-input并且只比较最后的计数器,将具有O(n)复杂度并且在所有情况下都在大约1 + 2*n + 1个操作中完成.这样的算法可以证明是整体的,比一个更好的算法更好,在最佳,平均和更差的情况下,分别是O(X),O((X + n)/ 2)和O(n). ,在这些相同的情况下,可以使用X*3,(X + n)*1.5和n*3操作.

Answer 2

此版本对于接近零或N的X值有效:

true_counter = 0
false_counter = 0
max_false = N - X

if(input 1)
   true_counter++
   if(counter >= X)
      return true
else
   false_counter++
   if(false_counter > max_false)
      return false

// and so on