algorithm - 求解递归 T(n) = T(n/3) + T(2n/3) + n^2？

我一直在尝试解决递归关系。重复次数是 T(n) = T(n/3)+T(2n/3)+n^2我解决了重复出现的 n 我把它作为 T(n)=nT(1)+ [ (9/5)(n^2)( (5/9)^(log n) ) ]谁能告诉我这个表达式的运行时间？ 最佳答案 我认为这种循环可以达到 Θ(n2)。为了看到这一点，我们将证明 T(n) = Ω(n2) 和 T(n) = O(n2)。表明 T(n) = Ω(n2) 非常简单——因为 T(n) 中有一个 n2 项，它肯定是 Ω(n2)。现在让我们证明 T(n) = O(n2)。我们有那个 考虑另一个重复: 由于 T(n) 增加并且 T(n) ≤ S(n)，S(n) 的任何上限也应该是 T(n) 的上限。使用 S(n) 上的主定理，我们有 a = 2，b = 3/2，和 c = 2。由于 logb a = log3/2 2 = 1.709511291... 我们已经证明了 T(n) = Ω(n2) 和 T(n) = O(n2)，所以 T(n) = Θ(n2)，如需要。希望这可以帮助!(顺便说一句 - (5/9)log n = (2log 5/9)log n = 2log n log 5/9 = (2log n)log 5/9 = nlog 5/9。这使得它更容易一些原因。)关于algorithm - 求解递归 T(n) = T(n/3) + T(2n/3) + n^2？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25717513/