performance - 如何为这个问题实现这个 O(1) 算法？

Question

我有变量x，还有函数f1(x), f2(x), .... fn(x)(n可以达到100万)。这些函数的值都是1或0。那么，如何编写算法，可以快速提取返回1的函数呢？谢谢。

在这里我展示我的。时间复杂度为O(n)，效率不够。

List funHaveTrueValues = new ArrayList();

for (int i=1; i<=n; ++i){
 if (fi(x)==true){
   funHaveTrueValues.add(fi);
  }
 }
}

有人可以提出 O(1) 算法吗？谢谢!

Answer 1

除非您对函数的了解比您告诉我们的多一点，否则不可能有 O(1) 算法。您必须至少查看每个函数的输出一次，使该问题的每个算法都在 Ω(n) 中运行。