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

Question

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

Или что-нибудь еще, что меньше, чем O (1)?

Answer 1

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

Теперь вы можете легко заменить g ( x ) на 1 / x ... очевидно, что приведенное выше определение все еще верно для некоторого f .

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

def get_faster(list):
    how_long = (1 / len(list)) * 100000
    sleep(how_long)

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

Но являются на самом деле реальными алгоритмами, где время выполнения может уменьшаться (по крайней мере, частично) при увеличении размера ввода. Обратите внимание, что эти алгоритмы не будут демонстрировать поведение во время выполнения ниже O (1). Тем не менее, они интересные. Например, возьмите очень простой алгоритм поиска текста: Horspool . Здесь ожидаемое время выполнения будет уменьшаться по мере увеличения длины шаблона поиска (но увеличение длины стога сена снова увеличит время выполнения).

Answer 2

Да.

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

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

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

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

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

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

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

Answer 6

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

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

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

void nothing() {};

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

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

Answer 7

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

Answer 8

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

Answer 9

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

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

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

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

Answer 10

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

|    |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 |