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

Question

这个问题的灵感来自我昨天正在研究的答案。

Let's say we have N inputs that evaluate to either true or false, what is the most efficient way to determine if X of those inputs are true?

注意事项:

1. The inputs are not in an array, so if you convert them to an array please account for any overhead costs.
2. By "most efficient" I mean in terms of best average case (although I would love to see best and worst case stats too).

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

1) 将变量视为电路的 bool 输入，并使用 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) 上。

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

技巧二: 短路评测
思路是回 false尽快(或不久之后)

打开的输入的运行计数大于 X 的数量(或者，如果我们正在计算关闭的输入的数量，当此计数超过 (n - X))

剩下要测试的输入数量加上打开的输入的运行计数小于 X。(或在计算关闭输入的情况下类似的东西)。

这个技巧相对简单，但计算早期退出测试中所需值的额外成本可能会抵消[静态]提前退出所带来的 yield 。

技巧三: 使用反向逻辑 :计算关闭而不是打开的输入数量。 (或两者都算)。
这种方法的成本/ yield 取决于要测试的输入数量(问题的 X)和我们可能对输入具有的统计先验(是在给定时间相对统一的输入数量)分布式还是我们倾向于只打开(或关闭)几个输入)。

solution proposed by Chris Acheson为 Trick 2 和 Trick 3 的使用提供了一个基线。假设我们可以对输入状态的分布做出一些假设，这个基线的额外性能改进将被驱动这样的“先验”:一些快速启发式之前完成输入的计数本身将决定我们是否应该计算哪个状态(打开或关闭或两者)，我们应该测试哪个限制等，并分支到算法的相应“版本”。

如果我们知道给定输入打开或关闭的个别概率，那么额外的 yield 也是可能的，因为我们将首先测试最可能(或最不可能)的可能性，以快速获得我们的“短路值”。

关于这些优化算法的最佳情况/最坏情况“复杂性”
假如说

在给定时间打开的输入数量是均匀分布的

所有输入在给定时间都有 50% 的变化

X 在 1 和 n 之间随机选择

技巧 #2 和 #3 的组合可能是 O(X/2)平均(我需要做数学计算，但这似乎是正确的)。但是我认为用 number of operations 来讨论更明智。相对于 X 和/或 n，而不是误用 O 符号...
假设所有操作大致产生相同的成本

初始化计数器或变量

测试输入或变量

加减法

等

计算给定算法完成所需的操作总数更容易也更准确，因此使用这些计数，用于各种最佳/最差/平均情况，以帮助决定特定算法。
为了说明这一点，一个简单的实现只是系统地对所有输入进行计数并仅在最后比较计数器，其复杂度为 O(n) 并且在所有情况下大约需要 1 + 2*n + 1 次操作。这样的算法可能被证明是整体的，比一个更高级的算法更好，比方说，在最好的、平均的和最坏的情况下分别是 O(X)、O((X+n)/2) 和 O(n)在这些相同的情况下，很可能使用 X*3、(X+n)* 1.5 和 n*3 运算。