T(n) = 2T(n/2) + n/2 的复杂性（没有大师定理）？

Question

我正在查看合并排序的最佳情况运行时间，并发现以下递归关系：T(n) = 2T(n/2) + n/2。我知道合并排序在所有情况下都是 theta(nlogn)。为了解决这个递归关系，我使用了伸缩：

T(n) = 2*T(n/2) + n/2
T(n) = 2^2*T(n/4) + n/4 + n/2
T(n) = 2^k*T(1) + (n/2 + n/4 + ... + n/2^k) 
2^k = n -> log_2(n) = k
T(n) = n + n(1/2 + 1/4 + ... + 1/n)

我不确定如何解决最后一部分的求和...我什至不确定这是否正确。我的想法是总计中会添加 log_2(n) 个项目？我不确定如何在不使用大师定理的情况下推导出 2T(n/2) + n/2 是 theta(nlogn) ...

Answer 1

正如评论中指出的那样，您的计算似乎有误。

T(n) = 2*T(n/2) + n/2
T(n) = 2*(2*T(n/4) + n/4) + n/2  = 4*T(n/4) + 2*(n/4) + n/2 = 4*T(n/4) + 2*(n/2)
T(n) = 4*(2*T(n/8) + n/8) + 2*(n/2) = 8*T(n/8) + (n/2) + 2*(n/2) = 8*T(n/8) + 3*(n/2)
...
T(n) = 2^k * T(n / 2^k) + k*(n/2),       2^k = n --->  k = log(n)
T(n) = log(n) * T(1) + log(n) * (n/2)
T(n) = logn + n*log(n)/2

因此归并排序的时间复杂度=O(n*log(n))

T(n) = 2T(n/2) + n/2 的复杂性（没有大师定理）？

Complexity of T(n) = 2T(n/2) + n/2 (without master's theorem)?

algorithm

time-complexity

big-o

mergesort