2016-06-26 61 views
5

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.

+0

La complessità del caso peggiore è 'O (infinito)' se è anche una cosa (quando 'x <= 1') – tkausl

+1

Sarà' log (n) 'nel caso' x * = c' (dove 'c 'è un certo * valore * costante * –

+0

@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

risposta

0

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).

4

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) 
4

Sia al valore originale di x, e assumere un> 1.

  • Dopo il primo ciclo, x = a ** 2
  • Dopo il secondo ciclo, x = a ** 4
  • Dopo il terzo ciclo, x = a ** 8
  • .. . Dopo il ciclo k-esimo, x = a ** (2 ** k)

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)) 
2

Let x valore iniziale è a, > 1. Ogni volta che il valore di x è un esponenziale di a e l'esponenziale raddoppia ogni volta, in quanto si quadratura il numero ogni iterazione.

Quindi il m termine è dato da enter image description here, dove m è il numero di cicli eseguiti. Quindi abbiamo bisogno di enter image description here o enter image description here, che è effettivamente enter image description here.