如何求解递推关系T(n)=T(n/3)+T(n/6)+1
How to solve the recurrence relation T(n)=T(n/3)+T(n/6)+1
一直在努力求解下一个递推关系T(n)=T(n/3)+T(n/6)+1
我不知道从哪里开始。想过先画个递归树再求解，不知道对不对
有人可以帮我解决这个问题吗？谢谢
您可以使用 Akra-Bazzi method，它是主定理的推广，用于解决具有不同大小的子问题的分而治之递归。它适用于以下形式的重复：
对于正常数 a，常数 b 在 (0,1) 中，g(n) 在 O(n^c) 中，h(n) 在 O(n/log^2(n)) 中。
在这种情况下：
按照该方法，我们需要 p 值使得：
求解 p 的方程得到 p=0.48954...
Akra-Bazzi 定理表示算法的复杂度为：
在给定 g(u) = 1 的情况下求解得到：
一直在努力求解下一个递推关系T(n)=T(n/3)+T(n/6)+1
我不知道从哪里开始。想过先画个递归树再求解，不知道对不对
有人可以帮我解决这个问题吗？谢谢
您可以使用 Akra-Bazzi method，它是主定理的推广，用于解决具有不同大小的子问题的分而治之递归。它适用于以下形式的重复：
对于正常数 a，常数 b 在 (0,1) 中，g(n) 在 O(n^c) 中，h(n) 在 O(n/log^2(n)) 中。
在这种情况下：
按照该方法，我们需要 p 值使得：
求解 p 的方程得到 p=0.48954...
Akra-Bazzi 定理表示算法的复杂度为：
在给定 g(u) = 1 的情况下求解得到：