Существуют ли реальные алгоритмы со сложностью O(1/n)?

Существуют ли реальные алгоритмы со сложностью O(1/n)? В голову лезет только ерунда по типу:

function test(n) {
  for (i=1; i<100000/n; i++) {
    dosomething();
  }
}

    

Ответы

Ответ 1

Их даже в теории не существует. Потому что это ограничение сверху.

O(C + 1/n) = O(C) = O(1)


Где C - некоторая константа, отличная от 0.

А 0 она не может быть равна, поскольку у нас в любом случае есть накладные расходы хотя бы на получение самого n и какое-то его использование.

Потому что если мы не используем n вообще, то сложность, очевидно, от него не зависи
и не может быть O(1/n). А если используем, то мы хоть раз к нему обратимся и константа будет ненулевой.



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



Даже в коде из вопроса


for (i=1; i<100000/n; i++) {



что произойдёт, когда n превысит 100000?

У нас будет ровно 4 операции: присваивание, деление, сравнение и выход из функции. Это O(1) - оно уже неспособно уменьшиться с ростом n.


Ответ 2

Нет, не существует.

Сначала вспомним, что такое асимптота:

Пусть у нас есть некая кривая y = A(x). Тогда асимптота y = B(x) — это такая кривая, к которой A как бы «прижимается» при движении в бесконечность вдоль оси x.

Графически это выглядит так:



Источник: https://en.wikipedia.org/wiki/File:1-over-x-plus-x.svg

В данном примере прямая y = x является асимптотой для y = 1 / x + x, так как пр
достаточно больших x обе линии практически сливаются.

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

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


Ответ 3

А вообще, есть интересный случай. В большинстве случаев говоря об асимптотике м
предполагаем возрастание аргумента. Но, строго говоря, это может быть не так. Например, если мы знаем, что область определения некоторой функции ограничена. Возьмём и реализуем деление int(1/x) через вычитание:



function f(x) {
  for (var i=0, v=1; v>0; ++i, v-=x);
  return i;
}

console.log(f(1));
console.log(f(.5));
console.log(f(.25));
console.log(f(.125));
console.log(f(.0625));
console.log(f(.0000001));




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