解决递归关系的时间复杂度？

Question

我正在做一个家庭作业问题，需要我比较 nlogn 和下面的重复。至于 nlogn 是否受以下时间复杂度的限制，上限或紧界。

   | 5             n = 1
 --| 2T(n/2) + n   n > 1

我认为 2T(n/2) + n 减少到 nlogn 但我不确定如何解决递推关系..

感谢您的帮助。

Answer 1

简答 - 您可以（并且应该）使用 "Master Theorem" 来查找此重复的 O-notation。

Master Theorem 是解决递归问题的便捷工具，它应该是您的首选，因为您可以快速得到结果。你可以用这个 exercise

得到一个 hands-on

Answer 2

解决复发（希望我做对了）：

2T(n/2) + n
2[2T(n/4) + n/2] + n
2^2*T(n/2^2) + 2n
you find the pattern if you keep on substituting new n
2^k*T(n/(2^k)) + kn
at this point you solve for closed form using the base case then n = 1
so for n/n = 1, we set 2^k = n, so k = logn
sub in k
2^(logn) * T(1) + (logn) * n

note that 2^logn = n with base 2 and T(1) = 5 for the base case
so we obtain 5n + nlogn
5n + nlogn is just O(nlogn)

因为我们都有 O(nlogn)，所以它是一个紧束缚或大 Theta。

或者，您也可以使用主定理轻松推导复杂性。万一你学会了。

a = 2
b = 2
c = 1

以上满足情况2，即Θ(nlogn)，参考wiki https://en.wikipedia.org/wiki/Master_theorem

解决递归关系的时间复杂度？

solving time complexity of a recurrance relation?

algorithm

complexity-theory

time-complexity