algorithm - 如何解决递归 T(n) = T(nc) +T(c) + n^2

Question

我有递归函数 T(n) = T(nc) +T(c) + n²

您能解释一下在以下情况下如何计算递归树的高度：

1. c有一个不确定的值
2. c = n/3 => T(n) = T(n-(n/3)) +T(n/3) + n²

我认为在第一种情况下 T(n) 成本 θ(n³) 和在第二种情况下 θ(n²)，对吗？

标签： algorithmtreerecurrence

Answer 1

1）如果c是一个常数，那么你可以忽略这个T(c)术语，它确实是θ(n³)。

2）当它是n/3或其他一些因素时，寻找T()具有最大系数的项n- 这会导致最长的分支。然后通过用这个替换所有其他项来给出时间复杂度的上限T。

示例：T(2n/3) + T(n/3) + n² < 2T(2n/3) + n²，从Master 定理来看，这确实是θ(n²)。