Существуют ли реальные алгоритмы со сложностью 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.
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.
