E 'mai possibile avere Big O meno di O (1)? [duplicare]

Question

  

Eventuali duplicati:
   ce ne sono O (1 / n) algoritmi?

E 'mai possibile che il codice sia Big O meno di O (1)?

Answer 1

O (1) significa semplicemente un'operazione tempo costante. Che il tempo potrebbe essere 1 nanosecondo o 1 milione di anni, la notazione non è una misura di tempo assoluto. A meno che, naturalmente, si sta lavorando sul sistema operativo per una macchina del tempo, che forse la funzione DoTimeTravel () avrebbe O (-1) la complessità: -)

Answer 2

Non proprio. O(1) è costante di tempo. Sia che si esprimono che come O(1) o O(2) o O(.5) fa davvero poca differenza per quanto puramente notazione O-grande va.

Come osservato in questa domanda , è tecnicamente possibile avere un O(1/n), ma che nessun algoritmo utile nel mondo reale soddisferebbe questo (anche se alcuni lo fanno algoritmo di hanno 1/n come parte della loro complessità algoritmica).

Answer 3

L'unica cosa che avrebbe preso meno di O (1) (costante di tempo) sarebbe un'operazione che ha fatto assolutamente nulla, e, quindi, ha preso tempo zero. Ma anche un NOP richiede solitamente un numero fisso di cicli ...