这个递归函数怎么用替换法求解呢？

Question

我有一个很奇怪的函数，看起来像这样：

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

我需要用替换法来解决这个问题，但我一直无法得出任何决定性的答案。

我需要解决步骤和大O

Answer 1

面对log时，像n = 2^k（k = log2(n)）这样的改变往往是一条出路：

n = 2^k

所以我们有

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

让我们看看它是什么意思：

T(2^k) = 2 * T(2^(k - 1)) + k * 2^k =
       = 2 * (2 * T(2^(k - 2)) + (k - 1) * 2^(k - 1)) + k * 2^k =
       = 4 * T(2^(k - 2)) + (k - 1) * 2^k + k * 2^k =
       = 4 * (2 * T(2^(k - 3)) + (k - 2) * 2^(k - 2)) + (k - 1) * 2^k + k * 2^k = 
       = 8 * T(2^(k - 3)) + (k - 2) * 2^k + (k - 1) * 2^k + k * 2^k = 
         ...
       = 2^k * T(0) + 2^k + 2 * 2^k + ... + k * 2^k =
       = 2^k * T(0) + 2^k (1 + 2 + ... + k) =
       = 2^k * T(0) + 2^k * k * (k + 1) / 2 =
       = 2^k * (T(0) + k * (k + 1) / 2)

到 return 到 n、n = log2(k) 的时间：

T(n) = n * (T(0) + log2(n) * (log2(n) + 1) / 2)

根据 O(n) 我们有

O(T(n)) = O(n * (T(0) + log2(n) * (log2(n) + 1) / 2)) =
        = O(n * (const + log2(n)^2 / 2 + log2(n) / 2) =
        = O(n * log2(n)^2 / 2) =
        = O(n * log2(n)^2) =
        = O(n * log(n)^2)

所以，答案是

O(T(n)) = O(n * log(n)^2)

请注意，由于 log2(n) == log(n, b) / log(2, b) 用于任意基数 b > 1 我们可以使用 log(n) 而不是 log2(n)

这个递归函数怎么用替换法求解呢？

How to solve this recurrence function with substition method?

algorithm

math

big-o

recurrence

substitution