Complessità algoritmo

[Superandri91]

Buonasera. Sto facendo degli esercizi di "informatica" in vista di un esame che avrò tra qualche settimana.
Ho un dubbio su un esercizio... Mi viene chiesto di calcolare la complessità di questo pseudocodice:

f(A):
n := A.length
i := 1
altre eventuali inizializzazioni eseguite in tempo costante
while i < n
do_something_in_tempo_costante
i := i*2
f(A[1..n/3])
f(A[n/3+1..(2/3)*n])
j := 2
while j < n*n
do_something_in_tempo_costante
j := j*j
return result

La soluzione dice che la complessità è T(N)=2T(n/3)+log(n)+log(log(n)), che poi può essere semplificata con il teorema del maestro...
La semplificazione l'ho capita, ma sinceramente non riesco a capire da dove viene questa soluzione... Immagino che la prima parte (2T(n/3)) venga dal fatto che all'interno del codice abbiamo due ricorsioni (una per il primo terzo, una per il secondo terzo dell'array), quindi la somma è 2T(n/3), correggetemi se sbaglio... Tuttavia non capisco da dove arrivano questi due log(n) nella seconda parte di T(n)!
Grazie in anticipo

[Superandri91]

Ok, penso di avere capito più o meno il motivo per cui trova i due log...
Per il primo, (log(n)) credo che ragiona sul fatto che il primo ciclo while termina quando i=n... Di conseguenza, poiché i vale 1, i valori che assume ogni ciclo sono 1,2,4,8,16,... ossia 2^0,2^1,2^3... Quindi, siccome devo trovare quante volte viene eseguito il ciclo pongo 2^x=n e quindi il ciclo termina quando x vale log(n)... Per quanto riguarda il secondo, faccio un ragionamento analogo e i valori che assume sono: 2,4,16,256... Quindi 2^(2^0),2^(2^1),2^(2^2),... Pongo ancora 2^(2^x)=n*n e ottengo loglog(n^2)... Dal momento che devo vedere quando j

Cita

Segnala