algorithm
Complessità dell'algoritmo
Ricerca…
Osservazioni
Tutti gli algoritmi sono una lista di passaggi per risolvere un problema. Ogni passaggio ha dipendenze su alcuni set di passaggi precedenti o l'inizio dell'algoritmo. Un piccolo problema potrebbe essere simile al seguente:
Questa struttura è chiamata grafico aciclico diretto, o DAG in breve. I collegamenti tra ciascun nodo nel grafico rappresentano le dipendenze nell'ordine delle operazioni e non ci sono cicli nel grafico.
Come si verificano le dipendenze? Prendi ad esempio il seguente codice:
total = 0
for(i = 1; i < 10; i++)
total = total + i
In questo psuedocode, ogni iterazione del ciclo for dipende dal risultato della precedente iterazione perché stiamo usando il valore calcolato nella precedente iterazione in questa successiva iterazione. Il DAG per questo codice potrebbe apparire come questo:
Se si capisce questa rappresentazione degli algoritmi, è possibile utilizzarla per comprendere la complessità dell'algoritmo in termini di lavoro e durata.
Lavoro
Il lavoro è il numero effettivo di operazioni che devono essere eseguite al fine di raggiungere l'obiettivo dell'algoritmo per una determinata dimensione di input n .
campata
A volte Span viene definito come percorso critico ed è il numero minore di passaggi che un algoritmo deve eseguire per raggiungere l'obiettivo dell'algoritmo.
L'immagine seguente evidenzia il grafico per mostrare le differenze tra lavoro e intervallo sul nostro DAG di esempio.
Il lavoro è il numero di nodi nel grafico nel suo complesso. Questo è rappresentato dal grafico a sinistra sopra. Lo span è il percorso critico, o il percorso più lungo dall'inizio alla fine. Quando il lavoro può essere svolto in parallelo, i nodi evidenziati in giallo a destra rappresentano l'intervallo, il minor numero di passaggi richiesti. Quando il lavoro deve essere fatto in serie, la durata è la stessa del lavoro.
Sia il lavoro che l'intervallo possono essere valutati indipendentemente in termini di analisi. La velocità di un algoritmo è determinata dallo span. La quantità di potenza di calcolo richiesta è determinata dal lavoro.
Notazione Big-Theta
A differenza della notazione Big-O, che rappresenta solo il limite superiore del tempo di esecuzione per alcuni algoritmi, Big-Theta è strettamente vincolato; sia superiore che inferiore. Il limite stretto è più preciso, ma anche più difficile da calcolare.
La notazione Big-Theta è simmetrica: f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))
Un modo intuitivo per afferrarlo è che f(x) = Ө(g(x)) significa che i grafici di f (x) e g (x) crescono nella stessa velocità, o che i grafici si comportano in modo simile per i grandi abbastanza valori di x.
L'espressione matematica completa della notazione Big-Theta è la seguente:
Ө (f (x)) = {g: N 0 -> R e c 1 , c 2 , n 0 > 0, dove c 1 <abs (g (n) / f (n)), per ogni n> n 0 e abs è il valore assoluto}
Un esempio
Se l'algoritmo per l'input n richiede 42n^2 + 25n + 4 operazioni per finire, diciamo che è O(n^2) , ma è anche O(n^3) e O(n^100) . Tuttavia, è Ө(n^2) e non è Ө(n^3) , Ө(n^4) ecc. Algoritmo che è Ө(f(n)) è anche O(f(n)) , ma Non viceversa!
Definizione matematica formale
Ө(g(x)) è un insieme di funzioni.
Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N}
Poiché Ө(g(x)) è un insieme, potremmo scrivere f(x) ∈ Ө(g(x)) per indicare che f(x) è un membro di Ө(g(x)) . Invece, di solito scriveremo f(x) = Ө(g(x)) per esprimere la stessa nozione - questo è il modo comune.
Ogni volta che Ө(g(x)) appare in una formula, la interpretiamo come una funzione anonima a cui non interessa nominare. Ad esempio l'equazione T(n) = T(n/2) + Ө(n) , significa T(n) = T(n/2) + f(n) dove f(n) è una funzione dell'insieme Ө(n) .
Sia f e g siano due funzioni definite su qualche sottoinsieme dei numeri reali. Scriviamo f(x) = Ө(g(x)) come x->infinity se e solo se ci sono costanti positive K e L e un numero reale x0 tale che detenga:
K|g(x)| <= f(x) <= L|g(x)| per tutti x >= x0 .
La definizione è uguale a:
f(x) = O(g(x)) and f(x) = Ω(g(x))
Un metodo che utilizza i limiti
se limit(x->infinity) f(x)/g(x) = c ∈ (0,∞) vale a dire il limite esiste ed è positivo, quindi f(x) = Ө(g(x))
Classi di complessità comuni
| Nome | Notazione | n = 10 | n = 100 |
|---|---|---|---|
| Costante | Ө (1) | 1 | 1 |
| logaritmica | Ө (log (n)) | 3 | 7 |
| Lineare | Ө (n) | 10 | 100 |
| linearitmico | Ө (n * log (n)) | 30 | 700 |
| quadratico | Ө (n ^ 2) | 100 | 10 000 |
| Esponenziale | Ө (2 ^ n) | 1 024 | 1.267650e + 30 |
| Fattoriale | Ө (n!) | 3 628 800 | 9.332622e + 157 |
Notazione Big-Omega
La notazione Ω viene utilizzata per il limite inferiore asintotico.
Definizione formale
Sia f(n) g(n) due funzioni definite sull'insieme dei numeri reali positivi. Scriviamo f(n) = Ω(g(n)) se ci sono costanti positive c e n0 tali che:
0 ≤ cg(n) ≤ f(n) for all n ≥ n0 .
Gli appunti
f(n) = Ω(g(n)) significa che f(n) cresce asintoticamente non più lentamente di g(n) . Possiamo anche dire di Ω(g(n)) quando l'analisi dell'algoritmo non è sufficiente per affermazioni su Θ(g(n)) o / e O(g(n)) .
Dalle definizioni delle notazioni segue il teorema:
Per due qualsiasi funzione f(n) g(n) abbiamo f(n) = Ө(g(n)) se e solo se f(n) = O(g(n)) and f(n) = Ω(g(n)) .
La notazione Ω graficamente può essere rappresentata come segue:
Ad esempio, abbiamo f(n) = 3n^2 + 5n - 4 . Quindi f(n) = Ω(n^2) . È anche corretto f(n) = Ω(n) , o anche f(n) = Ω(1) .
Un altro esempio per risolvere l'algoritmo di corrispondenza perfetta: se il numero di vertici è dispari, emettere "Nessun abbinamento perfetto", altrimenti provare tutti i possibili abbinamenti.
Vorremmo dire che l'algoritmo richiede un tempo esponenziale ma in realtà non è possibile dimostrare un limite inferiore Ω(n^2) usando la normale definizione di Ω poiché l'algoritmo gira in tempo lineare per n dispari. Dovremmo invece definire f(n)=Ω(g(n)) dicendo per alcuni costanti c>0 , f(n)≥ cg(n) per infinitamente molti n . Ciò fornisce una buona corrispondenza tra i limiti superiore e inferiore: f(n)=Ω(g(n)) iff f(n) != o(g(n)) .
Riferimenti
La definizione formale e il teorema sono tratti dal libro "Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli algoritmi".
Confronto delle notazioni asintotiche
Sia f(n) g(n) due funzioni definite sull'insieme dei numeri reali positivi, c, c1, c2, n0 sono costanti reali positive.
| Notazione | f (n) = O (g (n)) | f (n) = Ω (g (n)) | f (n) = Θ (g (n)) | f (n) = o (g (n)) | f (n) = ω (g (n)) |
|---|---|---|---|---|---|
| Definizione formale | ∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ cg(n) | ∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) ≤ f(n) | ∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) | ∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < cg(n) | ∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) < f(n) |
Analogia tra il confronto asintotico di f, g e numeri reali a, b | a ≤ b | a ≥ b | a = b | a < b | a > b |
| Esempio | 7n + 10 = O(n^2 + n - 9) | n^3 - 34 = Ω(10n^2 - 7n + 1) | 1/2 n^2 - 7n = Θ(n^2) | 5n^2 = o(n^3) | 7n^2 = ω(n) |
| Interpretazione grafica |  | |  |
Le notazioni asintotiche possono essere rappresentate su un diagramma di Venn come segue: 
link
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduzione agli algoritmi.
