• Non ci sono risultati.

Calcolo della complessità asintotica al caso peggiore di un algoritmo iterativo

N/A
N/A
Protected

Academic year: 2021

Condividi "Calcolo della complessità asintotica al caso peggiore di un algoritmo iterativo"

Copied!
2
0
0

Testo completo

(1)

Calcolo della complessità asintotica al caso peggiore di un algoritmo iterativo

Utilizzando la notazione asintotica O è possibile descrivere il tempo di esecuzione di un algoritmo al caso peggiore esaminando semplicemente la struttura complessiva dell’algoritmo.

 Le operazioni elementari (operazioni logico-aritmetiche e di assegnamento) se prive di chiamate di funzioni hanno tempo di esecuzione costante, quindi complessità O(1).

Se, al contrario, contengono chiamate di funzioni, il loro costo computazionale coincide con il costo delle funzioni chiamate.

 Il tempo di esecuzione di una chiamata di funzione è pari al tempo di esecuzione della funzione stessa più quello dovuto al calcolo dei parametri passati al tempo dell’invocazione,

 Il tempo di esecuzione di una sequenza S1 S2 … Ss di s≥2 istruzioni, ciascuna avente tempo di esecuzione Ti(n) = O(fi(n)) per 1 ≤ i ≤ s, è:

T(n) =

= O(max

i

{f

i

(n)})

 Costrutto di selezione

if(condizione) {

blocco then }else{

blocco else }

Uno solo tra i rami then ed else viene eseguito, in base al valore della condizione logica. Non potendo prevedere in generale tale valore (e quindi quale dei due blocchi sarà eseguito), siano:

o

T

condizione

(n)= O(f

condizione

(n))

o

T

then

(n)= O(f

then

(n))

o

T

else

(n)= O(f

else

(n))

il tempo di esecuzione di tale costrutto è il seguente:

T(n) = T

condizione

(n) + op(T

then

(n), T

else

(n))= O(max{f

condizione

(n)+

op(f

then

(n), f

else

(n))})

Dove op è max nel caso peggiore e min nel caso migliore, quindi nel caso peggiore:

T(n) = O(max{f

condizione

(n),f

then

(n),f

else

(n)})

(2)

 Costrutto iterativo for

for i=0 to m-1 {

blocco for }

T(n) =

(n) = O(m*max

i

{

(n)})

dove (n) è il tempo di esecuzione del blocco for all’iterazione i-esima del ciclo.

Più informalmente posso dire che:

T(n) = O(m*f

for

(n)) for i=0 to m

{

for j=0 to k {

blocco for }

}

T(n) =

(n) = O(m*k*max

j

{

(n)})

dove (n) è il tempo di esecuzione del blocco for interno all’iterazione j-esima del ciclo.

Più informalmente posso dire che:

T(n) = O(m*k*f

for

(n))

 Costrutto iterativo while

while(condizione) {

blocco while }

Sia m+1 il numero di volte in cui viene valutata la condizione logica del ciclo while. Sia Tcondizione_i(n) il tempo di valutazione della condizione logica all’iterazione i-esima del ciclo e Twhile_i(n) il tempo di esecuzione del blocco while all’iterazione i-esima. Poiché la condizione logica viene valutata una volta in più rispetto a quante volte viene eseguito il corpo, abbiamo il seguente tempo di esecuzione totale:

T(n) =

=

O(max{m*max

i

{f

condizione_i

(n)}, m*max

i

{f

while_i

(n)}})

Più informalmente posso dire che:

T(n) = O(m*(f

condizione

(n)+ f

while

(n)))

Riferimenti

Documenti correlati

(2) I tipi utilizzabili sono i tipi di dato semplice (un solo valore possibile per una variabile in un certo istante durante ’esecuzione dell’algoritmo) o tipo di dato

- Ω-grande, limite inferiore, del tempo di esecuzione per un qualunque input di dimensione N. • Analisi del

Irroratela quindi con un quarto di litro di vino e con altrettanto fumetto di pesce, poi passatela nel forno a 150 gradi per 45 minuti circa, unendo, a metà cottura, i

 Se nessuna variabile artificiale è ancora in base, ho una base fatta da sole colonne del problema originario e posso partire con Fase 2 su esso.  Se ho ancora variabili

Per poter valutare l’efficienza di un algoritmo, così da poterlo confrontare con algoritmi diversi che risolvono lo stesso problema, bisogna essere in grado di

Se tutte le iterazioni hanno lo stesso costo massimo, allora il costo dell’iterazione è pari al prodotto del costo massimo di una singola iterazione per il

Per poter valutare l’efficienza di un algoritmo, così da poterlo confrontare con algoritmi diversi che risolvono lo stesso problema, bisogna essere in grado di

Per poter valutare l’efficienza di un algoritmo, così da poterlo confrontare con algoritmi diversi che risolvono lo stesso problema, bisogna essere in grado di