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:

inserisci la descrizione dell'immagine qui

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:

inserisci la descrizione dell'immagine qui

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.

inserisci la descrizione dell'immagine qui

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:

Ω notazione

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 Notazione O Ω notazione Θ notazione

Le notazioni asintotiche possono essere rappresentate su un diagramma di Venn come segue: Notazioni asintotiche

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduzione agli algoritmi.



Modified text is an extract of the original Stack Overflow Documentation
Autorizzato sotto CC BY-SA 3.0
Non affiliato con Stack Overflow