Есть ли O (1 / n) алгоритмы? - PullRequest
Новая
       119

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

323 голосов
/ 25 мая 2009

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

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

Ответы [ 32 ]

0 голосов
/ 27 января 2019

Полагаю, меньше, чем O (1), невозможно. Любое время, занимаемое алгоритмом, называется O (1). Но для O (1 / n) как насчет функции ниже. (Я знаю, что есть много вариантов, уже представленных в этом решении, но я думаю, что у них всех есть некоторые недостатки (не основные, они хорошо объясняют концепцию). Так что вот один, просто для аргумента: 

def 1_by_n(n, C = 10):   #n could be float. C could be any positive number
  if n <= 0.0:           #If input is actually 0, infinite loop.
    while True:
      sleep(1)           #or pass
    return               #This line is not needed and is unreachable
  delta = 0.0001
  itr = delta
  while delta < C/n:
    itr += delta

Таким образом, при увеличении n функция будет занимать все меньше и меньше времени. Также гарантируется, что если input на самом деле равен 0, то функция вернется навсегда.

Можно утверждать, что оно будет ограничено точностью станка. таким образом, sinc eit имеет верхнюю границу, это O (1). Но мы также можем обойти это, взяв значения n и C в строку. И сложение и сравнение делается на строку. Идея состоит в том, что при этом мы можем уменьшить n сколь угодно малым. Таким образом, верхний предел функции не ограничен, даже если мы игнорируем n = 0.

Я также считаю, что мы не можем просто сказать, что время выполнения равно O (1 / n). Но мы должны сказать что-то вроде O (1 + 1 / n)

0 голосов
/ 25 мая 2009

Обозначение 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 не имеет значения)

Страница:
...