Aiutatemiiiiiiiiiiiiiiiiii! - Calcolo complessità algoritmi

[Xoom83]

Qualcuno sa spiegarmi come funziona il calcolo delle complessità di un algoritmo???????

[pietro84]

Qualcuno sa spiegarmi come funziona il calcolo delle complessità di un algoritmo???????

indichiamo con P(n) un problema di dimensione n e con A(k) un algoritmo che risolve tale problema in k passi di eleborazione.
è utile chiedersi come aumenta k all'aumentare della dimensione del problema n.
k=f(n).
per non dilungarci troppo la f(n) assume di solito i seguenti andamenti:
f(n)=n ----> classe lineare
f(n)=log(n) ----> classe logaritmica
f(n)=n^2 -----> classe quadratica

e così via

la funzione f(n) si ricava analizzando le righe di codice dell'algortimo, cioè vedendo come varia il numero di passi di elaborazione al variriare delle dimensioni del problema, ad esempio se in input c'è un array si può associare la dim del problema alla dimensione dell'array...

[Xoom83]

indichiamo con P(n) un problema di dimensione n e con A(k) un algoritmo che risolve tale problema in k passi di eleborazione.
è utile chiedersi come aumenta k all'aumentare della dimensione del problema n.
k=f(n).
per non dilungarci troppo la f(n) assume di solito i seguenti andamenti:
f(n)=n ----> classe lineare
f(n)=log(n) ----> classe logaritmica
f(n)=n^2 -----> classe quadratica

e così via

la funzione f(n) si ricava analizzando le righe di codice dell'algortimo, cioè vedendo come varia il numero di passi di elaborazione al variriare delle dimensioni del problema, ad esempio se in input c'è un array si può associare la dim del problema alla dimensione dell'array...

Fin qui ci sono,il mio problema è che non so come comportarmi nel caso di cicli annidati.....
Se ad esempio ho una serie di cicli annidati tra loro,la complessità totale a cosa è uguale?

[pietro84]

Fin qui ci sono,il mio problema è che non so come comportarmi nel caso di cicli annidati.....
Se ad esempio ho una serie di cicli annidati tra loro,la complessità totale a cosa è uguale?

di solito quando ci sono cicli annidati si fa il prodotto
n1*n2 dove n1 è il numero di iterazioni nel caso peggiore del primo ciclo e n2 è il numero di iteraz nel caso peggiore del secondo ciclo e così via
però l'analisi cambia leggermente a seconda dell'algoritmo specifico...