Ottimizzazione Algoritmica: Misurare l'Efficienza e la Complessità Computazionale
Classificato in Informatica
Scritto il in 
italiano con una dimensione di 3,42 KB
Principi di Progettazione e Misurazione dell'Efficienza Algoritmica
Ci sono diversi modi per risolvere un problema. Come scegliamo tra essi? Generalmente, nella progettazione di programmi informatici, si perseguono due obiettivi principali:
- La progettazione di un algoritmo che sia facile da capire, codificare e sottoporre a debug (Software Engineering).
- La progettazione di un algoritmo che faccia un uso efficiente delle risorse del computer (progettazione di algoritmi).
L'analisi degli algoritmi ci permette di misurare la difficoltà di un problema e valutare l'efficienza di un algoritmo.
Misurazione del Tempo di Esecuzione: Operazioni di Base
Non si può misurare il tempo in secondi, perché non esiste un computer standard di riferimento. Si misura invece il numero di operazioni di base o elementari.
Le operazioni di base vengono eseguite dal computer in un tempo limitato da una costante, ad esempio:
- Operazioni aritmetiche di base
- Assegnazione di tipi predefiniti
- Salti (chiamate a funzioni, procedure e ritorni)
- Confronti logici
- Strutture di accesso indicizzato di base (vettori e matrici)
È possibile studiare la complessità di un algoritmo basandosi solo su un piccolo insieme di istruzioni che influenzano il tempo di esecuzione (runtime).
Metodi per la Misurazione del Tempo di Esecuzione
Per misurare il tempo di esecuzione di un algoritmo, ci sono diversi metodi:
Benchmarking
La tecnica di riferimento è considerata come un insieme di input che rappresentano un carico di lavoro tipico per un programma.
Profiling
Consiste nell'associare a ogni istruzione di un programma un numero che rappresenta la frazione del tempo totale impiegato per eseguire quella particolare istruzione. Una delle tecniche più note (e informali) è la regola 90-10, la quale afferma che il 90% del tempo di esecuzione è speso nel 10% del codice.
Analisi Asintotica
Consiste nel raggruppare gli input in base alle loro dimensioni e stimare il tempo di esecuzione del programma per input di quelle dimensioni, T(n). Questa è la tecnica che verrà studiata in questo contesto.
Così, il tempo di esecuzione può essere definito come una funzione dell'input. Si indica T(n) come il tempo di esecuzione di un algoritmo per un input di dimensione n.
L'Efficienza Asintotica e la Notazione Asintotica
Il focus principale dell'analisi degli algoritmi risiede nel modo in cui il tempo di esecuzione cresce quando la dimensione dell'input aumenta. Questa è l'efficienza asintotica dell'algoritmo. Si chiama "asintotico" perché analizza il comportamento delle funzioni al limite, ovvero la loro crescita.
La notazione asintotica è descritta da una funzione il cui dominio sono i numeri naturali (N), basata sui tempi di esecuzione o sullo spazio di memoria degli algoritmi in relazione alla lunghezza dell'input. Si considerano funzioni asintoticamente non negative.
La notazione asintotica cattura il comportamento della funzione per grandi valori di N.
Le notazioni non dipendono dai tre casi precedentemente visti; è per questo che una notazione che determina il caso peggiore può essere presente in una o in tutte le situazioni.