Как реализовать этот алгоритм 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

Существует Алгоритм Гровера , который делает это в O (sqrt (n)), но для этого требуется квантовый компьютер.

Answer 3

Если , вы можете предположить, что каждый f равен O(1), тогда при совершении не более 1.000.000 вызовов к ним по-прежнему сохраняется постоянная верхняя граница . Таким образом, я полагаю, что ваш набросанный подход O(1), если вы ограничите его до 1.000.000 вызовов.

Редактировать

Поскольку я получил несколько отрицательных отзывов по этому поводу, я попытаюсь прояснить причину. Учитывая имеющуюся информацию, нет более быстрого способа решить эту проблему, чем оценить все f. Если вопрос действительно «Есть ли более быстрый / более умный способ сделать это?» , то ответ (как многие ответили) нет.

Если вопрос, однако, выполнен в стиле «Я получил этот вопрос на тесте теории сложности» (или подобном), то это может быть «уловка!». Это тот случай, к которому я стремился с моим ответом. В обобщенной задаче (с n функциями, без ограничений) временная сложность составляет O(n) при условии, что каждая функция ведет себя как O(1) oracle . Вводя крышу из 1.000.000 функций, сложность времени получает постоянную верхнюю границу O(1000000 * 1) = O(1).

Answer 4

Если x действительно изменится, вам все равно нужно будет оценить каждую функцию, поэтому она все равно будет O (n). Однако вы можете определить, для какого результата x может быть 0 или 1 (если возможно получить что-то вроде: x <= y always results in 0, x > y is always 1), и сохранить эти пороговые значения. Тогда вам нужно будет только оценить функции один раз, а потом просто проверить x по вычисленным порогам. Обратите внимание, что это сильно зависит от того, что на самом деле делает ваш fn (x).

Таким образом, ключ к чему-то, похожему на O (1), может быть кеширован, если результаты fn (x) кэшируются с разумными усилиями.

Answer 5

это невозможно, вы все равно должны запускать свои функции для всех n элементов, что означает n-функции

Answer 6

Вы должны оценить каждую функцию хотя бы один раз, и есть n функций.Поэтому вы не можете сделать лучше, чем O(n) (если, конечно, вы предварительно не вычислите выходные данные для всех возможных входов и сохраните их в таблице!).