Существуют ли реальные алгоритмы со сложностью O(1/n)?
1,00
р.
р.
Существуют ли реальные алгоритмы со сложностью O(1/n)? В голову лезет только ерунда по типу: function test(n) { for (i=1 i<100000/n i++) { dosomething() } } <br> Ответ Их даже в теории не существует. Потому что это ограничение сверху. 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++) {<br> что произойдёт, когда n превысит 100000? У нас будет ровно 4 операции: присваивание, деление, сравнение и выход из функции. Это O(1) - оно уже неспособно уменьшиться с ростом n.