Есть ли такая вещь как “отрицательная” большая-O сложность? [дубликат]

Не знаю, подходит ли это, но это напоминает мне о bittorrent. Чем больше людей скачивают файл, тем быстрее он загружается для всех них

Не совсем. O (1) - лучшее, на что можно надеяться.

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

обновление Чтобы прояснить ситуацию, я отвечаю на эту часть вопроса: Существуют ли какие-либо известные алгоритмы или проблемы, которые на самом деле легче или быстрее решать с большим объемом ввода?

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

В частности, автор ссылается на относительно простой алгоритм поиска подстроки:
http://en.wikipedia.org/wiki/Horspool

PS Но использование термина «отрицательная сложность» для таких алгоритмов не представляется возможным. разумно для меня.

Думать об алгоритме, который выполняется в отрицательное время, все равно, что думать о времени, идущем в обратном направлении.

Если программа начинает выполнение в 10:30 и останавливается в 10:00, не проходя через 11:00, она только что была выполнена с time = O (-1).

=]

Теперь по математической части:

Если вы не можете придумать последовательность действий, которые выполняются в обратном направлении (вы никогда не знаете ... lol) , доказательство довольно просто:

positiveTime = O (-1) означает:

positiveTime <= c * -1, для любого C> 0 и n> n0> 0

Рассмотрим ограничение «C> 0». Мы не можем найти положительное число, умножение которого на -1 даст другое положительное число. С учетом этого получается следующий результат:

positiveTime <= negativeNumber для любого n> n0> 0

Это просто доказывает, что у вас не может быть алгоритма с O (-1).

Ну, для многих вычислений типа "given input A return f(A)" можно "кэшировать" результаты вычислений (хранить их в массиве или карте), что сделает вычисления быстрее при большем количестве значений, ЕСЛИ некоторые из этих значений повторяются.

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

Это в некоторой степени применимо к алгоритмам сортировки - некоторые из них имеют сложность O(N) в лучшем случае и O(N^2) в худшем случае, в зависимости от состояния сортируемых данных.

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

Как и в случае с другим вопросом о пустом алгоритме, этот вопрос является вопросом определения, а не вопросом того, что возможно или невозможно. Конечно, можно придумать модель затрат, для которой алгоритм занимает O(1/n) время. (Это, конечно, не отрицательно, а скорее уменьшается с большим вкладом.) Алгоритм может делать что-то вроде sleep(1/n), как предлагается в одном из других ответов. Это правда, что модель затрат ломается, так как n отправляется в бесконечность, но n никогда не отправляется в бесконечность; каждая модель затрат в конечном итоге все равно ломается. Утверждение, что sleep(1/n) занимает O(1/n) время, может быть очень разумным для входного размера от 1 байта до 1 гигабайта. Это очень широкий диапазон для любой формулы сложности времени, чтобы быть применимым.

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