Algoritmo: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica Etichette: Annullato Modifica da mobile Modifica da web per mobile |
Nessun oggetto della modifica Etichette: Annullato Modifica da mobile Modifica da web per mobile |
||
Riga 196:
* l'algoritmo di Gauss non richiede altro spazio oltre a quello necessario per memorizzare la matrice dei coefficienti e il vettore dei termini noti. Al termine dell'algoritmo il vettore dei termini noti conterrà la soluzione. Pertanto la sua complessità spaziale è anch'essa minima: <math>O(n^2)</math>.
== Strutture di dati ==Un'ampia porzione della teoria degli algoritmi è lo studio della complessità, computazionale e spaziale. Vogliamo cioè sapere, al crescere della complessità del problema, in che modo cresce il tempo necessario a eseguire l'algoritmo e lo spazio di memoria occupato in un calcolatore.
La complessità di un algoritmo si misura asintoticamente. Vi sono quattro metodi per calcolare la complessità di un algoritmo:
metodo di sostituzione
metodo dell'iterazione
metodo dell'albero
metodo dell'esperto
Si definisce asintotica per due motivi
poiché ogni calcolatore può implementare algoritmi in modo differente, non si può stimare il tempo preciso
si vuole dare un'idea quantitativa di come l'algoritmo possa crescere in consumo di tempo all'aumentare dell'input, per valori sempre maggiori.
Presa una funzione associata a un algoritmo del tipo:
{{vedi anche|Struttura dati}}
| |||