Complessità computazionale

Un algoritmo A risolve un problema P se applicato a ogni sua istanza I ne produce la soluzione corretta.L' istanza di un problema invece è una particolare formulazione dello stesso quando alle variabili sono stati assegnati valori particolari.Il problema è costituito da descrizione generale e questione.Nella prima sono presenti i parametri che possono variare (variabili).La questione è costituita da un insieme di proprietà che la soluzione deve soddisfare.L' efficienza si calcola mediante parametri.

Tempo impiegato (complessità temporale);spazio utilizzato (complessità spaziale);quantità e modalità di input/output;tempo di trasmissione.DEVONO essere considerati.

"Semplicità" di comprensione/modificabilità del codice sorgente;"qualità di scrittura" del codice sorgente;accessibilità per l'utilizzo del programma;"bellezza grafica" dell'interfaccia utente.NON devono essere considerati.

Un algoritmo (programma) ha costo O(f(n)) o complessità O(f(n)) se esistono tre opportune costanti a, b, e n' tali che:tempo A(n) < a * f(n) + b per ogni n > n'O(f(n)) si dice limite inferiore al comportamento asintotico di una funzione.Una funzione g(n) è detta essere O-grande di un'altra funzione h(n), e viene scritta:g(n) è O(h(n)se esistono due costanti positive C e n' tali che per tutti i valori di n>=n' si abbia che:g(n) <= C * h(n)

ogni funzione polinomiale è O-grande di n elevato alla sua maggiore potenza;se f(n) è O(h(n)) e g(n) è O(h(n)) , allora f(n) + g(n) è O(h(n));se f(n) è O(h(n)) e g(n) è O(i(n)), allora f(n) * g(n) è O(h(n) * i(n));la funzione ank è O(nk);la funzione nk è O(nk + j) per ogni j positivo;se f(n) è O(g(n)) e g(n) è O(h(n)), allora f(n) è O(h(n)) (proprietà transitiva).

La complessità di un blocco costituito da più blocchi in sequenza è quella del blocco di complessità maggiore.

La complessità di un blocco costituito da più blocchi annidati è data dal prodotto delle complessità dei blocchi componenti.

Tp(n) = max { T(x), per ogni x istanza del problema}."P" indica che si considera il caso peggiore."n" indica la dimensione del problema.

Si definisce istruzione a costo unitario un' operazione (statement) la cui esecuzione non dipende nè dal valore nè dal tipo delle variabili, e prende il nome di passo base.Le seguenti istruzioni sono a costo unitario:assegnamento;operazioni di I/O (solo da tastiera e non da file);operazioni aritmetiche elementari;valutazione di espressioni booleane;accesso a elementi di un array.Si puo' avere una dimostrazione del conteggio dei passi base nel video allegato.

Complessità costanteTempo (n) = O(1)ad esempio scambio tra due variabili, lettura o scrittura nella posizione di un array, ecc.Complessità logaritmicaTempo (n) = O(log n)ad esempio la ricerca binaria.Complessità lineareTempo (n) = O(n)Complessità degli algoritmi con numero di operazioni proporzionale a n ( ricerca sequenziale, somma di numeri di n cifre; ecc.)Complessità pseudolineareTempo (n) = O(n log n)Ottimi algoritmi di ordinamento come il quick-sort, heap-sort ecc.Complessità nk, con k <= 2Tempo (n) = O(nk)Sono un esempio banali algoritmi di ordinamento come il bubble-sort (O(n2)), moltiplicazione di due matrici (O(n3)) ecc.Complessità esponenzialeTempo (n) = O(kn)Fanno parte gli algoritmi euristici, cioè quelli che procedono a tentativi, e anche il calcolo del fattoriale.

n non compare mai all'esponente.

n compare come esponente.

Dato un problema P e due algoritmi A e B che lo risolvono con complessità Tempo A(n) e Tempo B(n), diciamo che A è equivalente a B nel risolvere il problema P se:Tempo A(n) = O(Tempo B(n));Tempo B(n) = O(Tempo A(n)).

Si dice che f(n) ha complessità asintotica g(n) se valgono le seguenti condizioni:f(n) = O(g(n));g(n) è la più piccola di tutte le funzioni che soddisfano la condizione g(n) <= C * h(n).O(g(n)) rappresenta il limite inferiore al comportamento della funzione f(n) aventi lo stesso ordine.