recurrence is here!Как я могу решить следующую рекурсию, T (n) = 1, если n = 1, иначе T (n) = 2T (n/2) + logn, точно для n - степень 2?
Может кто-нибудь, пожалуйста, помогите мне?
Я знаю, первый шаг:
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)
им не очень хорошо с бревнами, может кто-то наставит меня через?
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
, где мы можем показать (1) следующим образом:
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
'Л.Г. (2^я)' является 'я Л.Г. (2)' (это просто 'я 'если' lg' является логарифмом базы-2). – Ryan
Положите повторение в свой вопрос, вопрос должен быть самодостаточным. – pjs
Я голосую, чтобы закрыть этот вопрос как не по теме, потому что это математический вопрос, а не вопрос программирования. –