Concetti Chiave
- Un algoritmo è una strategia composta da una sequenza finita di operazioni per risolvere un problema specifico.
- La complessità computazionale di un algoritmo dipende dalla dimensione e dai valori dei dati in ingresso, influenzando il tempo di esecuzione.
- Esistono diverse notazioni per descrivere la complessità, tra cui O, Ω e Θ, che rappresentano delimitazioni superiori, inferiori e simultanee del tempo di calcolo.
- La complessità globale di un algoritmo può essere determinata sommando le complessità di blocchi in sequenza o moltiplicandole in caso di blocchi annidati.
- La classificazione degli algoritmi distingue tra quelli a crescita polinomiale, risolvibili, e quelli a crescita esponenziale, non risolvibili.
Definizione di algoritmo
Un algoritmo è una strategia che serve per risolvere un problema ed è costituito da una sequenza finita di operazioni (dette anche istruzioni)
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.
Influenza dei dati in ingresso
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.
Notazioni di complessità
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 di complessità
● 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.
Complessità globale
● 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.
Operazione 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.
● 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.
Classificazione degli algoritmi
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
Domande da interrogazione
- Che cos'è un algoritmo e quali sono le sue caratteristiche principali?
- Come influiscono i dati in ingresso sulla complessità di un algoritmo?
- Cosa rappresentano le notazioni O, Ω e Θ nella valutazione della complessità?
- Qual è la differenza tra complessità globale di blocchi sequenziali e annidati?
- Come si classificano gli algoritmi in base alla loro complessità computazionale?
Un algoritmo è una strategia per risolvere un problema, costituita da una sequenza finita di operazioni. La sua complessità computazionale deve essere indipendente dalla macchina utilizzata e deve essere espressa in funzione dei dati in ingresso.
La complessità di un algoritmo dipende dal numero e dai valori dei dati in ingresso. Si considerano tre scenari per valutare il tempo di esecuzione: massimo, minimo e medio, a seconda dei valori che comportano rispettivamente il massimo e il minimo tempo di esecuzione.
La notazione O fornisce una delimitazione superiore del tempo di esecuzione, Ω una delimitazione inferiore, e Θ indica che un algoritmo ha sia una delimitazione superiore che inferiore, garantendo una valutazione precisa della complessità.
La complessità globale di blocchi sequenziali è data dalla complessità del blocco di maggiore complessità, mentre per blocchi annidati si calcola il prodotto delle complessità dei blocchi componenti.
Gli algoritmi possono essere classificati in due gruppi: quelli con crescita polinomiale (risolvibili e trattabili) e quelli con crescita esponenziale (non risolvibili e intrattabili).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo
