Please enable JavaScript.
Coggle requires JavaScript to display documents.
COMPLESSITA' COMPUTAZIONALE - Coggle Diagram
COMPLESSITA' COMPUTAZIONALE
qualità
di un algoritmo
bisogna valutare:
spazio di memoria
tempo di esecuzione
-soluzioni semplici
-indipendenti dal linguaggio di programmazione
-facilmente modificabili
valutare il
costo
di un algoritmo
i misura in
numero di operazioni
che l’algoritmo deve compiere per fornire i risultati
Il
tempo
di esecuzione di un algoritmo è proporzionale
al suo costo
complessità e valori
dei dati in ingresso
è legata ai dati in input in base a:
dimensione
disposizione
valori
3 tipi:
caso medio
caso pessimo
caso ottimo
algoritmo con la minima complessità
efficienza di un algoritmo
due algoritmi appartenenti alla
stessa classe di complessità
possono essere confrontati relativamente al
tempo di esecuzione
appartengono alla stessa classe di complessità se:
lim (n → ∞) f₁(n) / f₂(n) = C con C > 0 costante
ordine di grandezza
e classi di computabilità
complessità asintotica
valutare la complessità per valori molto grandi delle dimensioni del problema
diverse classi di complessità:
costante, logaritmica, lineare, n log(n), polinomiale, esponenziale
complessità computazionale
dimensione del problema
= numero di operazioni di un algoritmo è legato alla dimensione dei dati di input