Algoritmo che applicato a tutte le istanze di un problema ne da la soluzione corretta.
misura l'efficienza di i/o rispetto a stazioni remote
occupazione di memoria da parte del programma
il tempo necessario all'esecuzione dell'algoritmo
si da il valore di un passo base alle operazioni elementari
una possibile formulazione di un problema quando alle sue variabili sono stati assegnati valori particolari
tutti gli input che hanno la stessa dimensione
esprime il tempo necessario affinchè l'algoritmo possa produrre la soluzione di un'istanza di dimensione n.
si dice che f(n) ha complessità asintotica g(n) se f(n) è uguale a O(g(n)) e contemporaneamente g(n) è la piu piccola di tutte le funzioni che soddisfano la condizione g(n)<= c*h(n)
una funzione g(n) è detta essere O-grande di un altra funzione h(n) se esistono due costanti positive c ed l tali che per tutti i valori n >=l si abbia che g(n)<= c*h(n)
si indica con n log n;gli algoritmi quick-sort e heap-sort sono un esempio di questa categoria.
indicata con O(n) è tipica degli algoritmi con operazioni proporzionali.
indicata con O(1) , tipica degli algoritmi che eseguono lo stesso numero di operazioni indipendentemente da n.
si indica con n!
si indica con O (log n). è tipico dell'algoritmo di ricerca binaria.
è tipica degli algoritmi come il bubble-sort(O(n^2)) o moltiplicazione tra matrici O(n^3).
dato un algoritmo il cui costo di esecuzione è T(n),un'istruzione di tale algoritmo è detta dominante quando,per ogni intero n,essa viene eseguita un numero d(n)di volte tale che T(n) <a*d(n)+b ,con a e b opportune costanti.
la complessità di un blocco costituito da piu blocchi in sequenza è quella del blocco di complessità maggiore
la complessità di un blocco costituito da piu blocchi annidati è data dal prodotto delle complessità.