Kategorier: Alle - efficienza - memoria - complessità - algoritmo

av giorgia raco 7 år siden

170

complessita computazionale

La complessità asintotica si riferisce alla caratterizzazione di una funzione in termini di un'altra funzione, fornendo un'indicazione della sua crescita. L'algoritmo risolutore è in grado di risolvere correttamente tutte le istanze di un problema, e la sua performance viene spesso misurata in termini di tempo e spazio.

complessita computazionale

teorema del prodotto

la complessità di un blocco costituito da piu blocchi annidati è data dal prodotto delle complessità.

teorema della somma

la complessità di un blocco costituito da piu blocchi in sequenza è quella del blocco di complessità maggiore

proprietà algebriche

istruzione dominante

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.

n^k

è tipica degli algoritmi come il bubble-sort(O(n^2)) o moltiplicazione tra matrici O(n^3).

logaritmica

si indica con O (log n). è tipico dell'algoritmo di ricerca binaria.

fattoriale

si indica con n!

costante

indicata con O(1) , tipica degli algoritmi che eseguono lo stesso numero di operazioni indipendentemente da n.

lineare

indicata con O(n) è tipica degli algoritmi con operazioni proporzionali.

pseudo lineare

si indica con n log n;gli algoritmi quick-sort e heap-sort sono un esempio di questa categoria.

classi di complessità

notazione O grande

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)

complessità asintotica

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)

funzione T(n)

esprime il tempo necessario affinchè l'algoritmo possa produrre la soluzione di un'istanza di dimensione n.

cardinalità (n)

tutti gli input che hanno la stessa dimensione

caso peggiore

assegnazione

somma algebrica

input e output da tastiera

operazioni booleane

accesso ad array

istanze

una possibile formulazione di un problema quando alle sue variabili sono stati assegnati valori particolari

passi base

si da il valore di un passo base alle operazioni elementari

temporale

il tempo necessario all'esecuzione dell'algoritmo

input e output (escluso da file)

spaziale

occupazione di memoria da parte del programma

trasmissione

misura l'efficienza di i/o rispetto a stazioni remote

semplicità del codice

grafica

oggettivi

soggettivi

parametri

algoritmo risolutore

Algoritmo che applicato a tutte le istanze di un problema ne da la soluzione corretta.

complessita computazionale