divide-and-conquer - T(n) = 2T(n/2) + log n を解く

Question

T(n) = 2T(n/2) + log n を解こうとしています

置換 n = 2^k

T(2^k) = 2T(2^(k-1)) + k  
T(2^k) = 2^2 T(2^(k-1)) + 2(k-1) + k

after k steps
T(2^k) = 2^k T(1) + 2^(k-1) + 2 * (2^(k-2)) +....+k

したがって、基本的には i*2^i の項を合計する必要があります。ここで、i = 1 で n - 1 をログに記録します
。これらの項を合計する簡単な方法を見つけることができませんでした。私は何か間違っていますか？この再帰を解決する他の方法はありますか? マスター定理は彼女に効くでしょうか? はいの場合、どのように？

ありがとう。

Answer 1

Wolfram|Alphaは閉形式解を与える：

初期条件によって固定される定数 c_1 の場合。

ちなみに、log(n)/log(2) = lg(n) で、lg は 2 を底とする対数です。

Answer 2

まず、再帰的なエクスポートを定義する必要があります。T(1) とします。T(2^k) = 2T(2^(k-1)) + k; * g(k) = T(2^k)/2^k と定義します。次に * に入ります: g(k) = g(k-1) + k/2^k = g(1) + sum(i/2^i); i=2,3,4...k g(1) = T(1)/2 = c;

次に、合計式を展開して定義できます = y; 次に、y/2 の式を展開します。yy/2 は等比数列なので解けます

私が解決したように、合計 = 3/2 - (k+2)/2^k;

したがって、T(n) = 2^k * g(k) = (3/2+c)*n - (2+logn)