|
|
Per la soluzione di un problema posso esistere algoritmi diversi, quale scegliere allora? Quale richiede meno “tempo di calcolo”? Poiché i problemi da risolvere hanno una dimensione che dipende dalla grandezza dei dati in input, viene spontaneo esprimere il tempo di calcolo come il costo complessivo delle operazioni elementari, in funzione della dimensione n dei dati in ingresso. Sono considerate elementari le operazioni aritmetiche, logiche, di confronto e di assegnamento. Consideriamo la seguente funzione scritta in linguaggio C, che implementa una algoritmo che dato un insieme di numeri interi aj,……,ak determina il numero di valore minimo.
Analizziamo il costo di ciascuna riga di questo programma.
Il tempo di calcolo T(n) sarà quindi:
Analizziamo lo stesso programma ottenuto questa vola con un algoritmo ricorsivo, ovvero una procedura che richiama se stessa per la risoluzione di un problema.
Se vi è un solo elemento il tempo di calcolo è dato dalla somma di c1+c2+c5 e quindi il tempo di calcolo è costante t(1)=c. Nel caso n>1 la funzione suddivide l’ array in due porzioni, la prima contente un solo elemento e l’ altra contente i rimanenti n-1, e richiama se stessa sulla seconda porzione, la cui dimensione è n-1. Di conseguenza vale che:
Una tecnica utile per risolvere relazioni di ricorrenza consiste nel produrre una catena di uguaglianze, ottenute per sostituzioni successive:
Quindi anche questa funzione richiede un tempo di calcolo che cresce linearmente in n, come il tempo di calcolo della versione non ricorsiva. In generale, nel valutare il tempo di calcolo T(n), è molto difficile quantificare con esattezza il numero di operazioni elementari eseguite. Questa difficoltà viene aggirata valutando il numero di operazioni in ordine di grandezza, ovvero come limitazione della funzione T(n), al tendere all’ infinito della dimensione n, trascurando le costanti. Si parla quindi di complessità computazionale asintotica in ordine di grandezza, o brevemente complessità di una procedura.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.