algorithm - 如何使用替换法解决以下递归问题？

Question

我需要使用替换方法证明以下递归的紧界:

T(n) = 2T(n/2) + n/log(n)

我已经到了 Substitution 方法的“猜测”部分，并且知道 T(n) 是 O(n*log(log(n)))通过使用递归树和迭代方法。但是我很难弄清楚如何从 big-O 和 Omega 的归纳步骤开始:

Assume  T(n/2) <= c*(n/2)log(log(n/2))
T(n) = 2T(n/2) + n/log(n) <= 2c*(n/2)log(log(n/2)) + n/log(n)

Assume  T(n/2) => c*(n/2)log(log(n/2))
T(n) = 2T(n/2) + n/log(n) => 2c*(n/2)log(log(n/2)) + n/log(n)

Answer 1

假设

T(n/2) <= (n/2) log log (n/2) = (n/2) log (log n - 1).

然后

T(n) = 2T(n/2) + n/log n
     <= n log (log n - 1) + n/log n
     = n log log n - n (log log n - log (log n - 1) + 1/log n),

所以足以证明 log log n - log (log n - 1) >= 1/log n ，这是一般不等式的一个例子 log k - log (k - 1) >= 1/k , 通过积分证明 1/x来自 x = k - 1至 x = k并应用中值定理。 (从视觉上看，宽度为 1 和高度为 1/k 的矩形符合 1/x 从 x = k - 1 到 x = k 的曲线。)

下界类似；使用不等式log k - log (k - 1) <= 1/(k - 1) <= 2/k对于 k >= 2 .