by giorgia raco 7 years ago
170
More like this
la complessità di un blocco costituito da piu blocchi annidati è data dal prodotto delle complessità.
la complessità di un blocco costituito da piu blocchi in sequenza è quella del blocco di complessità maggiore
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.
è tipica degli algoritmi come il bubble-sort(O(n^2)) o moltiplicazione tra matrici O(n^3).
si indica con O (log n). è tipico dell'algoritmo di ricerca binaria.
si indica con n!
indicata con O(1) , tipica degli algoritmi che eseguono lo stesso numero di operazioni indipendentemente da n.
indicata con O(n) è tipica degli algoritmi con operazioni proporzionali.
si indica con n log n;gli algoritmi quick-sort e heap-sort sono un esempio di questa categoria.
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 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)
esprime il tempo necessario affinchè l'algoritmo possa produrre la soluzione di un'istanza di dimensione n.
tutti gli input che hanno la stessa dimensione
una possibile formulazione di un problema quando alle sue variabili sono stati assegnati valori particolari
si da il valore di un passo base alle operazioni elementari
il tempo necessario all'esecuzione dell'algoritmo
occupazione di memoria da parte del programma
misura l'efficienza di i/o rispetto a stazioni remote
Algoritmo che applicato a tutte le istanze di un problema ne da la soluzione corretta.
