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

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

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

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

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

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

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

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

Нет ничего меньше 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) минимально возможной вычислительной сложностью

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

пустота ничего () {};

И даже это спорно

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

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

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

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

(Если мы решим не делать этого, тогда это может стать вопросом Дзэн или Дао ... в мире программирования, O (1) по-прежнему является минимумом).

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

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

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

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

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

Это невозможно. Определение 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, оценка не изменится.

Да.

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

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

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

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 или меньше инструкций.

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

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

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

у многих был правильный ответ (Нет) Вот другой способ доказать это: Чтобы иметь функцию, нужно вызвать функцию, и нужно вернуть ответ. Это занимает определенное постоянное количество времени. КАЖДЫЙ РАЗ, если остальная часть обработки занимает меньше времени для больших входов, распечатка ответа (который, как мы можем предположить, является одним битом) занимает, по крайней мере, постоянное время.

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

def f( *args ): 
  if len(args)<1:
    args[1] = 10

Эта функция работает быстрее, если добавлен необязательный второй аргумент, потому что в противном случае он должен быть назначен. Я понимаю, что это не уравнение, но на страницах википедии говорится, что big-O также часто применяется к вычислительным системам.

Существуют подлинейные алгоритмы. Фактически, поиск Algorithm - очень хороший пример одного.