Qual è la differenza tra O (1) e Θ (1)?

Question

Conosco le definizioni di entrambi, ma qual è la ragione a volte vedo O (1) e altre volte Θ (1) scritto nei libri di testo?

Grazie.

Answer 1

La notazione Big-O esprime un limite superiore asintotico, mentre la notazione Big-Theta esprime inoltre un limite inferiore asintotico. Spesso, il limite superiore è ciò a cui le persone sono interessate, quindi scrivono O (qualcosa), anche quando Theta (qualcosa) sarebbe anche vero. Ad esempio, se volessi contare il numero di cose che sono uguali a x in una lista non ordinata, potresti dire che può essere fatto in tempo lineare ed è O (n), perché ciò che conta per te è che ha vinto ' t prendere più a lungo di quello. Tuttavia, sarebbe anche vero che è Omega (n) e quindi Theta (n), dal momento che devi esaminare tutti gli elementi della lista - non può essere fatto in tempo sub-lineare.

Answer 2

O (1) e Θ (1) non sono necessariamente gli stessi se si parla di funzioni su numeri reali. Ad esempio, considera la funzione f (n) = 1/n. Questa funzione è O (1) perché per ogni n ≥ 1, f (n) ≤ 1. Tuttavia, è Θ (1) per il seguente motivo: una definizione di f (n) = Θ (g (n)) è il limite di | f (n)/g (n) | come n va all'infinito c'è un valore finito L che soddisfa 0 < L. Inserendo f (n) = 1/n e g (n) = 1, prendiamo il limite di | 1/n | come n va all'infinito e ottieni che sia 0. Pertanto, f (n) ≠ Θ (1).

Spero che questo aiuti!