Algoritmi e calcolo della complessità

Algoritmo

Un algoritmo è una strategia che serve per risolvere un problema ed è costituito da una sequenza finita di operazioni (dette anche istruzioni)

Complessità algoritmo

La valutazione della complessità computazionale deve soddisfare due requisiti:

1.

Non deve dipendere da una particolare macchina o da un particolare compilatore: il tempo di esecuzione di ogni istruzione in un qualunque linguaggio non è uguale per tutti i calcolatori ma varia (es: dipendenza della frequenza di lavoro della cpu )

2. Deve essere espressa in funzione dei dati in ingresso: un algoritmo elabora dei dati in ingresso per fornire altri dati che rappresentano la soluzione del problema, il tempo di esecuzione dell'algoritmo varia al variare dei dati in ingresso.
Tempo di esecuzione→ relativo sia alla dimensione dei dati in ingresso che al loro valore.
Dati di ingresso→ La complessità di un algoritmo dipende sempre dal numero dei dati che devono essere elaborati dall'algoritmo (Dimensione dei dati in ingresso=n).
Valori assunti dai dati in ingresso→ In molti casi la complessità computazionale di un algoritmo dipende anche da questi.

Al fine di tener conto dell'influenza dei valori assunti dai dati in ingresso sulla complessità computazionale, in genere vengono considerati 3 possibili scenari: un tempo di calcolo massimo, minimo e uno medio:

Massimo: T(n) viene fissato considerando i valori dei dati in ingresso che comportano il massimo tempo di esecuzione.
Minimo: T(n) viene fissato considerando i valori dei dati in ingresso che comportano il minimo tempo di esecuzione.
Medio: il tempo medio di esecuzione su dati di dimensione n, ottenuto considerando tutti i possibili valori dei dati in ingresso, per ciascuno di essi determinando la complessità computazionale e, infine, eseguendo la media dei valori di complessità computazionale ottenuti.

Complessità asintotica

Notazione O→ fornisce una delimitazione superiore al tempo di esecuzione di un algoritmo, cioè fornisce una valutazione approssimata per eccesso.

Notazione ohm→ fornisce una delimitazione inferiore al costo di esecuzione di un algoritmo.

Classi di complessità→ grazie all’analisi della complessità asintotica possiamo categorizzare gli algoritmi nelle seguenti classi di complessità:
● costante O(1)
● logaritmica O (logn)
● lineare O (n)
● nlog O (nlogn)
● quadratica O (n2)
● cubica O (n3)
● esponenziale O (an) a > 1

Efficienza: O (1)

Delimitazioni superiori e inferiori per gli algoritmi

● Un algoritmo ha complessità O(f(n)) se è Tworst(n) = O(f(n)).
In tal caso f(n) è infatti una delimitazione superiore del tempo di calcolo per qualsiasi input: si ha la garanzia che al crescere di n il tempo di calcolo non cresce di più di f(n), qualunque sia l'input.

● Un algoritmo ha complessità Ω(f(n)) se è Tbest(n) = Ω(f(n)).
In tal caso f(n) è infatti una delimitazione inferiore del tempo di calcolo per qualsiasi input: si ha purtroppo la certezza che al crescere di n il tempo di calcolo cresce almeno come f(n), qualunque sia l'input.

● Un algoritmo ha complessità Θ(f(n)) se ha complessità O(f(n)) e Ω(f(n)).
In tal caso f(n) è infatti una delimitazione sia inferiore che superiore del tempo di calcolo per qualsiasi input.

Algebra degli “O” grandi

● Sia g1(n) la complessità del primo blocco e g2(n) la complessità del secondo blocco. La complessità globale è:
O(g1(n) + g2(n)) = O(max{g1(n), g2(n)})
La complessità di un blocco costituito da più blocchi in sequenza è quella del blocco di complessità maggiore

● Sia g1(n) la complessità del blocco esterno e g2(n) la complessità di quello interno. La complessità globale è:
O(g1(n) * g2(n)) = O(g1(n)) * O(g2(n))
La complessità di un blocco costituito da più blocchi annidati è data dal prodotto delle complessità dei blocchi componenti.

Istruzione dominante

Si chiama operazione dominante o caratteristica di un algoritmo l’operazione che viene
eseguita con maggiore frequenza; nel caso di operazioni eseguite con la stessa frequenza si considera quella più onerosa in termini di tempo impiegato per la sua esecuzione.

Calcolo della complessità

● si considera il numero di dati tendente a infinito, ovvero si calcola la complessità asintotica di un determinato algoritmo
● contempla di norma il peggior caso possibile

Complessità computazionale

“La complessità computazionale si occupa della valutazione del costo degli algoritmi in termini di risorse di calcolo, quali il tempo di elaborazione e la quantità di memoria utilizzata. Nel contesto della complessità computazionale vengono anche studiati i costi intrinseci alla soluzione dei problemi, con l‘obiettivo di comprendere le prestazioni massime raggiungibili da un algoritmo applicato.

Si possono suddividere le classi in due gruppi:
● algoritmi con crescita polinomiale in n→ risolvibile, trattabile
● algoritmi con crescita esponenziale in n→ non risolvibili, intrattabili