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

Question

我有变量x,函数f1(x),f2(x),... fn(x)(n最多可达1百万).这些函数的值是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)运行.

Answer 2

有格罗弗的算法,其IT在O(开方(N)),但它需要一个量子计算机.