请验证我的逻辑，看看我正在尝试的内容是有效的还是可疑的。
W(n) = W(n/2) + nlg(n)
W(1) = 1
n =2^k
通过尝试模式
line 1 : W (2^k) = W(2^k-1) + nlgn
line 2 : = W(2^k-2) + nlgn + nlgn
...
line i : = W(2^k-i) + i*nlgn
然后为 i 解决剩下的问题。
我只是想确保如果我在一个地方（在第 1 行）用 2 k替换而不是在另一个地方替换n lg n.
我发现通过替换2^k for 2^k lg(2^k)真的很油腻。
欢迎任何想法（特别是如果我应该在 2^k 中替换，如果我应该那么你会如何建议解决方案）
可以根据需要在 n 和 2 k之间来回切换，因为您假设 n = 2 k。但是，这并不意味着您上面的内容是正确的。请记住，随着 n 的减小，n log n 的值也不断减小，因此语句并非如此
线 i = W(2 k-i ) + i * n lg n
是真的。
让我们再使用一次迭代方法：
W(n) = W(n / 2) + n log n
= (W(n / 4) + (n/2) log (n/2)) + n log n
= W(n / 4) + (n/2) (log n - 1) + n log n
= W(n / 4) + n log n / 2 - n / 2 + n log n
= W(n / 4) + (1 + 1/2) n log n - n / 2
= (W(n / 8) + (n / 4) log(n/4)) + (1 + 1/2) n log n - n / 2
= W(n / 8) + (n / 4) (log n - 2) + (1 + 1/2) n log n - n / 2
= W(n / 8) + n log n / 4 - n / 2 + (1 + 1/2) log n - n / 2
= W(n / 8) + (1 + 1/2 + 1/4) n log n - n
= (W(n / 16) + (n / 8) log(n/8)) + (1 + 1/2 + 1/4) n log n - n
= W(n / 16) + (n / 8) (log n - 3)) + (1 + 1/2 + 1/4) n log n - n
= W(n / 16) + n log n / 8 - 3n / 8 + (1 + 1/2 + 1/4) n log n - n
= W(n / 16) + (1 + 1/2 + 1/4 + 1/8) n log n - n - 3/8n
我们可以看看这个，看看我们是否发现了一个模式。首先，请注意，随着我们不断向外扩展，n log n 项的系数为 (1 + 1/2 + 1/4 + 1/8 + ...)。该级数收敛到 2，因此当迭代停止时，该项将介于 n log n 和 2n log n 之间。接下来看-n项的系数。如果你仔细观察，你会注意到这个系数是 -1 倍
（1 / 2 + 2 / 4 + 3 / 8 + 4 / 16 + 5 / 32 + ...）
这是 i / 2 i的总和，收敛到 2。因此，如果我们迭代这个过程，我们会发现每一步的值是 Θ(n log n) - Θ(n)，所以整体递归求解到 Θ(n log n)。
希望这可以帮助！