Есть ли O (1 / n) алгоритмы?

Question

Есть ли O (1 / n) алгоритмы?

Или что-нибудь еще, что меньше, чем O (1)?

Answer 1

Я считаю, что квантовые алгоритмы могут выполнять несколько вычислений "одновременно" посредством суперпозиции ...

Сомневаюсь, что это полезный ответ.

Answer 2

у многих людей был правильный ответ (Нет). Вот еще один способ доказать это: для того, чтобы иметь функцию, вы должны вызвать функцию и вернуть ответ. Это занимает определенное постоянное количество времени. ДАЖЕ ЕСЛИ для остальной обработки потребовалось меньше времени для больших входных данных, распечатка ответа (который мы можем считать единичным битом) занимает, по крайней мере, постоянное время.

Answer 3

Какие проблемы становятся легче по мере роста населения? Один из ответов - это нечто вроде bittorrent, где скорость загрузки является обратной функцией числа узлов. В отличие от автомобиля, который замедляется при загрузке, сеть с общим доступом к файлам, такая как bittorrent, ускоряет подключение большего количества узлов.

Answer 4

Вы не можете опуститься ниже O (1), однако O (k), где k меньше N, возможно. Мы назвали их алгоритмами сублинейного времени . В некоторых задачах алгоритм сублинейного времени может дать только приблизительные решения конкретной задачи. Однако иногда приблизительные решения просто хороши, возможно, из-за того, что набор данных слишком велик или слишком дорог для вычислений, чтобы вычислить все.

Answer 5

Если решение существует, оно может быть подготовлено и доступно в постоянное время = немедленно. Например, используя структуру данных LIFO, если вы знаете, что сортирующий запрос для обратного порядка. Затем данные уже отсортированы, учитывая, что была выбрана подходящая модель (LIFO).

Answer 6

Как уже указывалось, кроме возможного исключения нулевой функции, не может быть O(1/n) функций, так как время, которое потребуется, должно приблизиться к 0.

Конечно, есть некоторые алгоритмы, подобные определенным Конрадом, которые, кажется, должны быть меньше, чем O(1), по крайней мере, в некотором смысле.

def get_faster(list):
    how_long = 1/len(list)
    sleep(how_long)

Если вы хотите исследовать эти алгоритмы, вы должны либо определить собственное асимптотическое измерение, либо свое собственное представление о времени. Например, в приведенном выше алгоритме я мог бы разрешить использование ряда «свободных» операций определенное количество раз. В приведенном выше алгоритме, если я определяю t ', исключая время для всего, кроме сна, тогда t' = 1 / n, что равно O (1 / n). Вероятно, есть лучшие примеры, поскольку асимптотическое поведение тривиально. На самом деле, я уверен, что кто-то может придумать чувства, которые дают нетривиальные результаты.

Answer 7

O (1 / n) не меньше, чем O (1), это означает, что чем больше у вас данных, тем быстрее работает алгоритм. Скажем, вы получаете массив и всегда заполняете его до 10 ¹⁰⁰ элементов, если у него меньше этого, и ничего не делаете, если есть больше. Это, конечно, не O (1 / n), а что-то вроде O (-n) :) Слишком плохая запись O-big не допускает отрицательных значений.

Answer 8

Большинство остальных ответов интерпретируют big-O как исключительно время выполнения алгоритма. Но поскольку в вопросе об этом не упоминалось, я подумал, что стоит упомянуть другое применение big-O в численном анализе, которое связано с ошибкой.

Многие алгоритмы могут быть O (h ^ p) или O (n ^ {- p}) в зависимости от того, говорите ли вы о размере шага (h) или количестве делений (n). Например, в методе Эйлера вы ищите оценку y (h), учитывая, что вы знаете y (0) и dy / dx (производная от y). Ваша оценка y (h) тем точнее, чем ближе h к 0. Таким образом, чтобы найти y (x) для некоторого произвольного x, нужно взять интервал от 0 до x, разбить его до n частей и запустить метод Эйлера в каждой точке переходить от y (0) к y (x / n) к y (2x / n) и т. д.

Таким образом, метод Эйлера - это алгоритм O (h) или O (1 / n), где h обычно интерпретируется как размер шага, а n - как число раз, которое вы делите интервал.

Вы также можете иметь O (1 / ч) в реальных приложениях для численного анализа из-за ошибок округления с плавающей запятой . Чем меньше ваш интервал, тем больше отмена происходит при реализации определенных алгоритмов, тем больше потери значащих цифр и, следовательно, больше ошибок, которые распространяются через алгоритм.

Для метода Эйлера, если вы используете числа с плавающей запятой, используйте достаточно маленький шаг и отмену, и вы добавляете небольшое число к большому, оставляя большое число без изменений. Для алгоритмов, которые вычисляют производную путем вычитания друг от друга двух чисел из функции, вычисленной в двух очень близких положениях, аппроксимирующих y '(x) с (y (x + h) - y (x) / h), в гладких функциях y (x + h) приближается к y (x), что приводит к большой отмене и оценке производной с меньшим количеством значащих цифр. Это, в свою очередь, будет распространяться на любой алгоритм, для которого требуется производная (например, краевая задача).

Answer 9

Может быть возможно построить алгоритм, который будет O (1 / n). Одним примером может быть цикл, который повторяет несколько кратных f (n) -n раз, где f (n) - это некоторая функция, значение которой гарантированно больше n, а предел f (n) -n при n приближается к бесконечности нуль. Вычисление f (n) также должно быть постоянным для всех n. Я не знаю, как выглядит f (n) или какое приложение будет иметь такой алгоритм, на мой взгляд, однако такая функция может существовать, но полученный алгоритм не будет иметь никакой иной цели, кроме как доказать возможность алгоритма с O (1 / п).

Answer 10

Если ответ один и тот же независимо от входных данных, то у вас есть алгоритм O (0).

или другими словами - ответ известен до отправки входных данных - функция может быть оптимизирована - поэтому O (0)