Prerequisito – Notazioni asintotiche , Proprietà delle notazioni asintotiche , Analisi degli algoritmi
1. Notazione O grande (O):
È definito come limite superiore e il limite superiore su un algoritmo è la maggior quantità di tempo richiesta (la prestazione nel caso peggiore).
Notazione O grande è usato per descrivere il limite superiore asintotico .
Matematicamente, se f(n) descrive il tempo di esecuzione di un algoritmo; f(n) È O(g(n)) se esiste una costante positiva C E n0 tale che,
0 <= f(n) = n0
N = usato per dare una funzione al limite superiore.
Se una funzione è SU) , lo è automaticamente O(n-quadrato) anche.
Esempio grafico per Grande O:
cos'è un carattere speciale
2. Notazione del grande Omega (Ω):
È definito come limite inferiore e limite inferiore su un algoritmo è la minima quantità di tempo richiesta (il modo più efficiente possibile, in altre parole il caso migliore).
Proprio come O notazione fornire un limite superiore asintotico , OH notazione fornisce limite inferiore asintotico .
Permettere f(n) definire il tempo di esecuzione di un algoritmo;
f(n) si dice che sia Ω(g(n)) se esiste una costante positiva C E (n0) tale che
0 <= Cg(n) = n0
albero binario vs albero di ricerca binario
N = utilizzato per indicare il limite inferiore di una funzione
Se una funzione è Ω(n-quadrato) lo è automaticamente Oh(n) anche.
Esempio grafico per Grande Omega (Ω):
3. Notazione Big Theta (Θ):
È definito come il limite più stretto e il limite più stretto è il migliore di tutti i tempi peggiori che l'algoritmo può assumere.
Permettere f(n) definire il tempo di esecuzione di un algoritmo.
f(n) si dice che sia Θ(g(n)) Se f(n) È O(g(n)) E f(n) È Ω(g(n)).
Matematicamente,
0 <= f(n) = n0
0 <= C2g(n) = n0Unendo entrambe le equazioni, otteniamo:
0 <= C2g(n) <= f(n) = n0
L'equazione significa semplicemente che esistono costanti positive C1 e C2 tali che f(n) è un sandwich tra C2 g(n) e C1g(n).
Esempio grafico di Grande Theta (Θ) :
Java divide la stringa per delimitatore
Differenza tra Big oh, Big Omega e Big Theta:
| Si No. | Grande O | Grande Omega ( OH) | Grande Theta (IO) |
|---|---|---|---|
| 1. | È come (<=) il tasso di crescita di un algoritmo è inferiore o uguale a un valore specifico. | È come (>=) il tasso di crescita è maggiore o uguale a un valore specificato. | È come (==) il che significa che il tasso di crescita è uguale a un valore specificato. |
| 2. | Il limite superiore dell'algoritmo è rappresentato dalla notazione Big O. Solo la funzione di cui sopra è delimitata da Big O. Il limite superiore asintotico è dato dalla notazione Big O. | Il limite inferiore dell’algoritmo è rappresentato dalla notazione Omega. Il limite inferiore asintotico è dato dalla notazione Omega. | Il limite della funzione dall'alto e dal basso è rappresentato dalla notazione theta. L'esatto comportamento asintotico è ottenuto da questa notazione theta. |
| 3. | Big O – Limite superiore | Grande Omega (Ω) – Limite inferiore | Big Theta (Θ) – Limite stretto |
| 4. | È definito come limite superiore e limite superiore su un algoritmo è la maggior quantità di tempo richiesta (la prestazione nel caso peggiore). | È definito come limite inferiore e limite inferiore su un algoritmo è la minima quantità di tempo richiesta (il modo più efficiente possibile, in altre parole il caso migliore). | È definito come il limite più stretto e il limite più stretto è il migliore di tutti i tempi peggiori che l'algoritmo può assumere. |
| 5. | Matematicamente: Big Oh è 0 <= f(n) = n0 | Matematicamente: il Grande Omega è 0 <= Cg(n) = n0 | Matematicamente – Big Theta è 0 <= C2g(n) <= f(n) = n0 |
Per maggiori dettagli consultare: Progettazione e analisi di algoritmi .