Существуют ли какие-либо O (1/n) алгоритмы?

да.

существует ровно один алгоритм с временем выполнения O (1/n), "пустой" алгоритм.

для алгоритма, чтобы быть O (1/n) означает, что он выполняет асимптотически в меньшем количестве шагов, чем алгоритм, состоящий из одной инструкции. Если он выполняется менее чем за один шаг для всех n > n0, он должен состоять из точно никакой инструкции вообще для тех n. поскольку проверка "если n > n0" стоит по крайней мере 1 инструкции, она не должна состоять из инструкции для всех Н.

подводя итоги: Единственным алгоритмом, который является O (1 / n), является пустой алгоритм, состоящий из нет инструкция.

Это невозможно. Определение Big-O-это не больше неравенство:

A(n) = O(B(n))
<=>
exists constants C and n0, C > 0, n0 > 0 such that
for all n > n0, A(n) <= C * B(n)

таким образом, B(n) на самом деле является максимальным значением, поэтому, если оно уменьшается по мере увеличения n, оценка не изменится.

sharptooth правильно, О(1) является наилучшей производительности. Однако это не означает быстрого решения, просто фиксированное время решения.

интересный вариант, и, возможно, то, что действительно предложил, какие проблемы легче по мере роста населения. Я думаю 1, хотя и надуманный и неискренний ответ:

есть ли два человека в наборе имеют тот же день рождения? Когда n превышает 365, верните true. Хотя для менее чем 365, это O (n ln n). Возможно, это не отличный ответ, так как проблема не медленно становится легче, а просто становится O(1) для n > 365.

из моего предыдущего изучения нотации big O, даже если вам нужен 1 шаг (например, проверка переменной, выполнение задания), это O(1).

обратите внимание, что O(1) совпадает с O(6), потому что "константа" не имеет значения. Вот почему мы говорим, что O(n) - это то же самое, что O(3n).

Так что если вам нужен даже 1 шаг, Это O(1)... и поскольку ваша программа, по крайней мере, нуждается в 1 шаге, минимальный алгоритм может идти O(1). Разве если мы этого не сделаем, то это O(0), я думаю? Если мы это сделаем все, что угодно, тогда это O (1), и это минимум, на который он может пойти.

или как насчет этого:

программист: Босс, я нашел способ сделать это в O(1) раз!
босс: нет необходимости делать это, мы обанкротились сегодня утром.
программист: о, тогда он становится O (0).

Как насчет того, чтобы вообще не запускать функцию (NOOP)? или используя фиксированное значение. Это считается?

нет, это невозможно:

поскольку n стремится к бесконечности в 1/n, мы в конечном итоге достигаем 1 / (inf), что фактически равно 0.

таким образом, класс big-oh проблемы будет O (0) с массивным n, но ближе к постоянному времени с низким n. это неразумно, так как единственное, что можно сделать быстрее, чем постоянное время:

void nothing() {};

и даже это спорно!

Как только вы выполните команду, вы, по крайней мере O (1), поэтому нет, у нас не может быть большого класса O(1/n)!

Я часто использую O(1/n) для описания вероятностей, которые становятся меньше по мере увеличения входных данных-например, вероятность того, что Справедливая монета выходит на хвосты при переворотах log2(n), равна O (1/n).

O (1) просто означает "постоянное время".

когда вы добавляете ранний выход в цикл[1], Вы (в нотации big-O) превращаете алгоритм O(1) в o(n), но делаете это быстрее.

фишка В общем алгоритм постоянного времени является лучшим, и линейный лучше, чем экспоненциальный, но для небольших количеств n экспоненциальный алгоритм может быть на самом деле быстрее.

1: предполагая, что длина статического списка для этого примера

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

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

для тех, кто читает этот вопрос и хочет понять, о чем идет разговор, это может помочь:

|    |constant |logarithmic |linear|  N-log-N |quadratic|  cubic  |  exponential  |
|  n |  O(1)   | O(log n)   | O(n) |O(n log n)|  O(n^2) |  O(n^3) |     O(2^n)    |
|  1 |       1 |          1 |     1|         1|        1|       1 |             2 |
|  2 |       1 |          1 |     2|         2|        4|       8 |             4 |
|  4 |       1 |          2 |     4|         8|       16|      64 |            16 |
|  8 |       1 |          3 |     8|        24|       64|     512 |           256 |
| 16 |       1 |          4 |    16|        64|      256|   4,096 |         65536 |
| 32 |       1 |          5 |    32|       160|    1,024|  32,768 | 4,294,967,296 |
| 64 |       1 |          6 |    64|       384|    4,069| 262,144 |   1.8 x 10^19 |

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

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

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

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

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

как было указано, кроме возможного исключения функции null, не может быть никакого 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). Вероятно, есть лучшие примеры, поскольку асимптотическое поведение тривиально. На самом деле, я уверен, что кто-то там может придумать чувств, которые дают нетривиальные результаты.

большинство остальных ответов интерпретируют 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 / h) в реальных приложениях численного анализа, из-за ошибки округления с плавающей запятой. Чем меньше вы делаете свой интервал, тем больше происходит отмена для реализации определенных алгоритмов, больше потерь значащих цифр и, следовательно, больше ошибок, которые распространяются через алгоритм.

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

хорошо, я немного подумал об этом, и, возможно, существует алгоритм, который может следовать этой общей форме:

вам нужно вычислить проблему коммивояжера для графа 1000 узлов, однако вам также предоставляется список узлов, которые вы не можете посетить. По мере того как список недоступных узлов увеличивается, проблему становится легче решить.

Как насчет этого:

void FindRandomInList(list l)
{
    while(1)
    {
        int rand = Random.next();
        if (l.contains(rand))
            return;
    }
}

по мере увеличения размера списка ожидаемое время выполнения программы уменьшается.

Я вижу алгоритм, который является O(1/n), по общему признанию, к верхней границе:

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

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

Это имеет наихудшую производительность бесконечности, но средняя производительность случая, которая снижается по мере заполнения пространства данных.

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

class Function
{
    public double[] ApproximateSolution(double tolerance)
    {
        // if this isn't sub-constant on the parameter, it's rather useless
    }
}

У меня были такие сомнения еще в 2007 году, приятно видеть эту тему, я пришел к этой теме из моей Reddit thread - > http://www.reddit.com/r/programming/comments/d4i8t/trying_to_find_an_algorithm_with_its_complexity/

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

Я не знаю об алгоритмах, но сложности меньше, чем O(1) появляются в рандомизированных алгоритмах. На самом деле, o(1) (немного o) меньше, чем O(1). Такая сложность обычно появляется в рандомизированных алгоритмах. Например, как вы сказали, когда вероятность какого-либо события имеет порядок 1/n, они обозначают его с помощью o(1). Или когда они хотят сказать, что что - то происходит с высокой вероятностью (например, 1 - 1/n), они обозначают это 1-o(1).

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

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

обозначение Big-O представляет худший сценарий для алгоритма, который не то же самое, что его типичное время выполнения. Легко доказать, что алгоритм O(1/n) является алгоритмом O(1). По определению
O (1/n) --> T (n) = C > 0
O (1/n) --> T (n) =C
O (1/n) --> O( 1), так как нотация Big-O игнорирует константы (т. е. значение C не имеет значения)

не меньше, чем O(1) Обозначение Big-O подразумевает наибольший порядок сложности для алгоритма

если алгоритм имеет время выполнения n^3 + n^2 + n + 5, то это O(n^3) Низшие силы здесь вообще не имеют значения, потому что как n -> Inf, n^2 будет неуместным по сравнению с n^3

точно так же, как n -> Inf, O(1/n) будет неуместным по сравнению с O(1), следовательно, 3 + O(1/n) будет таким же, как O(1), что делает O(1) наименьшей возможной вычислительной сложностью

inline void O0Algorithm() {}

вот простой алгоритм O(1/n). И даже делает что-то интересное!

function foo(list input) {
  int m;
  double output;

  m = (1/ input.size) * max_value;  
  output = 0;
  for (int i = 0; i < m; i++)
    output+= random(0,1);

  return output;
}

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