求解递归 T(n) = T(n/2) + 2T(n/4) + n？
Solving recurrence T(n) = T(n/2) + 2T(n/4) + n?
我正在使用我朋友的 pdf（算法解锁）研究递归并尝试解决有关递归的问题，但我还不清楚递归树的机制（我认为这是要解决的方法用于此问题）以及如何使边界变紧，例如我希望常数变小？
首先，看看给出的建议 并在发布问题之前尝试做一些事情。我回答这个只是因为我发现刷新我的技能很有趣。
解决方案是O(n log(n))。
所以你必须看到大师定理在这里不起作用，但是Akra-Bazzi会起作用。
所以这里 g(n) = n、a1 = 1、b1 = 1/2、a2 = 2、b2=1/4。解方程：a1*b1^p + a2*b2^p = 1 你得到 p = 1。
现在求解从 1 到 x 的积分 int(1/u)du 你将得到 log(x)。所以复杂度是 O(x(1+log(x))，也就是 O(nlog(n))，其中 O 是紧界。
尝试使用递归树扩展递归。
你会得到这样的东西：
看到每一关的非递归复杂度=n
通过扩展 T(n)，我们有 2 个不同高度的子树。
可以看到2个高度H1和H2。
现在 T(n) 受限于 2 个子树的复杂度：
n * H1 >= T(n) >= n * H2
在哪里：
H1 = 1+log_2(n) 和 H2 = 1+log_4(n)
所以解是 O(nlog_2(n))
我正在使用我朋友的 pdf（算法解锁）研究递归并尝试解决有关递归的问题，但我还不清楚递归树的机制（我认为这是要解决的方法用于此问题）以及如何使边界变紧，例如我希望常数变小？
首先，看看给出的建议
解决方案是O(n log(n))。
所以你必须看到大师定理在这里不起作用，但是Akra-Bazzi会起作用。
所以这里 g(n) = n、a1 = 1、b1 = 1/2、a2 = 2、b2=1/4。解方程：a1*b1^p + a2*b2^p = 1 你得到 p = 1。
现在求解从 1 到 x 的积分 int(1/u)du 你将得到 log(x)。所以复杂度是 O(x(1+log(x))，也就是 O(nlog(n))，其中 O 是紧界。
尝试使用递归树扩展递归。 你会得到这样的东西：
看到每一关的非递归复杂度=n 通过扩展 T(n)，我们有 2 个不同高度的子树。 可以看到2个高度H1和H2。
现在 T(n) 受限于 2 个子树的复杂度： n * H1 >= T(n) >= n * H2
在哪里： H1 = 1+log_2(n) 和 H2 = 1+log_4(n)
所以解是 O(nlog_2(n))