2017-02-19 4 views
-1

recurrence is here!Wie kann ich die folgende Wiederholung lösen, T (n) = 1 wenn n = 1, sonst T (n) = 2T (n/2) + logn, genau für n eine Potenz von 2?

Kann mir bitte jemand helfen?

Ich weiß, dass der erste Schritt ist:

n = 2^i 
T(2^i)=5T(2^i/2) + lg(2^i) 
T(2^i)=5T(2^i-1) + lg(2^i) 
define t(i) = T(2^i) 
t(i)-5t(i-1)-lg(2^i) 

im nicht sehr gut mit Scheitholz, kann mir jemand führen durch?

+0

'lg (2^i)' ist 'i lg (2)' (das ist nur 'i 'wenn' lg' der Logarithmus zur Basis 2 ist. – Ryan

+0

Setzen Sie die Wiederholung in Ihre Frage ein, die Frage sollte in sich geschlossen sein. – pjs

+0

Ich stimme ab, diese Frage als off-topic zu schließen, weil es eine mathematische Frage ist, keine Programmierfrage. –

Antwort

-1

T(n) = 2*T(n/2) + lg(n)

= (2^2*T(n/2^2) + 2*lg(n/2)) + lg(n) 

= 2^3*T(n/2^3) + 2^2*lg(n/2^2) + 2*lg(n/2) + lg(n) 

... ... ... 

= 2^i*T(n/2^i) + 2^(i-1)*lg(n/2^(i-1)) + 2^(i-2)*lg(n/2^(i-2)) + .. + 2*lg(n/2^1) + lg(n) 

= n*T(1) + 2^(i-1)*lg(2) + 2^(i-2)*lg(2^2) + .. + 2*lg(2^(i-1)) + lg(2^i), where n = 2^i 

= n*1 + (2^(i-1) + 2*2^(i-2) + 3*2^(i-3) + ... + (i-1)*2 + i*1) 

= n + (2^(i+1) - 2 - i) .... (1) 

= n + 2*n - 2 - lg(n) 

= 3*n - lg(n) - 2 

wo können wir zeigen, (1) wie folgt:

S =   2^(i-1) + 2*2^(i-2) + 3*2^(i-3) + ... + (i-1)*2 + i*1 (3) 
2*S = 2^(i) + 2*2^(i-1) + 3*2^(i-2) + 4*2^(i-3) + ... + (i)*2   (4) 

(4) - (3) => S = 2^(i) + (2^(i-1) + 2^(i-2) + 2^(i-3) + ... + 2) - i 
       = 2^(i) + 2*(2^(i-1) - 1)/(2-1) - i 
       = 2^i + 2^i - 2 - i 
       = 2^(i+1) - 2 - i 
Verwandte Themen