Ciao Qualcuno può aiutarmi con la domandaAlgoritmo costo utilizzando teorema
T(n)=T(n^(1/2)) + theta (lg lg n)
Questo è quello che ho fatto finora Let
m = lg n
s(m)=s(m/2) + theta (lg m)
Applicando teorema qui
a=1 b=2
m^log 2 (1) = m^0 =1
ora bloccato.
si dispone di:
a = 1, b = 2
f(m) = Ө(lg(m))
Il secondo caso del teorema si applica se:
f(m) = Ө(m^c * lg^k(m))
dove:
c = log_b(a)
Testing questo fuori, abbiamo:
f(m) = Ө(lg(m)) = Ө(m^0 * lg(m))
-> c = 0
-> c = log_b(a) = log_2(1) = 0
Si applica quindi il secondo caso . La soluzione della ricorrenza è quindi:
T(m) = Ө(m^c * lg²(m)) = Ө(lg²(m))
Sostituendo m, arriviamo indietro
T(n) = Ө(lg²(lg(n)))
È un prerequisito tuttavia che' b> 1' per il teorema principale? –
Penso che dovrebbe essere 'T (m) = Ө (m^c * lg² (m)) = Ө (lg² (m)) ', così che' T (n) = Ө (lg² (lg (n))) '. – Teepeemm
@Teepeemm Sì, hai ragione. Buona cattura –
Primo, T (n) = T (n^(1/2)) + theta (lg lg n) può essere scritto come
T (2^(2^k)) = T (2^(2^(k-1))) + theta (k).
L'aggregazione dell'equazione di cui sopra per k = 1 a d dà T (2^(2^d)) = theta (d^2). Sia n = 2^(2^d), otteniamo T (n) = theta ((lg lg n)^2).
@ TAN shoudnt essere k + 1 nella seconda riga ?? – aneena
@aneena è radice quadrata: (2^(2^k))^(1/2) = 2^(2^k/2) = 2^(2^(k-1)). –
'n^(1/2) = sqrt (n)', e '(lg n)/2! = Sqrt (n)', quindi il tuo lavoro finora sembra sbagliato. Devi assolutamente usare il Metodo Master? – IVlad
@IVlad 'lg (sqrt (n)) == lg (n)/2 == m/2' (per definizione). Non è corretto? –
@Asad - sì, è corretto. Ma l'OP ha 'T (sqrt (n))', e non vedo come abbia ottenuto da quello a 'T (lg (sqrt (n)) = T (m/2)'. Sarebbe corretto se aveva 'T (lg sqrt (n))'. – IVlad