recursion - 如何从特殊的 Mergesort 计算复杂度

Question

我尝试从 Mergesort 计算复杂度。标准合并排序具有递归 T(n) = T(n/2)+T(n/2)+n 所以它很容易用主定理计算。

但我的问题是，如何计算 T(n) = T(2n/3) + T(n/3) + n 和 T(n) = T(n-100) + T(100) 的合并排序？

你们能帮帮我吗？谢谢 =)

Answer 1

这两个例子是计算递归方程的教科书例子。

要解决它们，您需要使用“递归树”方法。

我知道第一个条件的答案是 theta(nlogn) ，第二个条件的答案是 theta(n^2) 。现在要找到解决方案，我认为您可以从 CLRS 算法简介中的递归树中获得一个很好的视角。