La risposta corretta è log (log (n)), posso vedere il log (n) poiché x^k> = n è quando il ciclo while si fermerà. quindi ho avuto modo di accedere (n), cosa mi manca?Qual è la complessità temporale di questo ciclo while?
P.S: è dato che x = 2.
La risposta corretta è log (log (n)), posso vedere il log (n) poiché x^k> = n è quando il ciclo while si fermerà. quindi ho avuto modo di accedere (n), cosa mi manca?Qual è la complessità temporale di questo ciclo while?
P.S: è dato che x = 2.
Edit: (Given x = 2)
tua risposta sarebbe corretta se:
while(n>x)
x*=2;
Questo significa che il tempo per raggiungere il risultato è tagliato in mezzo ad ogni iterazione.
Ma poiché il tempo è ridotto di x
ogni iterazione e x
è in aumento, riceverai O log(Log(n))
.
Log(n)
è la complessità in cui si salta a metà di ogni iterazione (B-Tree).
Espandere il loop (lasciare x = 2
) e vedrete:
x = 2
x = 4 // 2 * 2
x = 16 // 4 * 4
x = 256 // 16 * 16
x = 65536 // 256 * 256
...
x = 2 ** (2 ** n) // you can prove this by induction
e così
n = log(log(x))
sarete perfettamente ragione con n = log(x)
stima se avete x *= constant
corpo, per esempio per la constant == 2
abbiamo
x = 2
x = 4
x = 8
...
x == 2 ** n
dove n
è solo
n = log(x)
Sia al valore originale di x, e assumere un> 1.
x> = n significa
a**(2**k) >= n
2**k >= log(n)/log(a)
k >= log2(log(n)/log(a)) = log2(log(n))-log2(log(a))
La complessità del caso peggiore è 'O (infinito)' se è anche una cosa (quando 'x <= 1') – tkausl
Sarà' log (n) 'nel caso' x * = c' (dove 'c 'è un certo * valore * costante * –
@tkausl O (infinito) non è una cosa, e non supponendo che x> 1 sia una precondizione rende il tutto" non un algoritmo "in primo luogo – harold