计算递归关系的时间复杂度 f(n) = f(n/2) + f(n/3)

Question

如何计算递归关系的时间复杂度f(n) = f(n/2) + f(n/3)。我们在 n=1 和 n=0 处有基本情况。

如何计算一般情况下的时间复杂度，即 f(n) = f(n/x) + f(n/y)，其中 x

Edit-1 :（在发布第一个答案后）考虑的每个数字都是整数。

Edit-2 :(在发布第一个答案后）我喜欢 Mbo 给出的答案，但是是否可以通过制作树等来回答这个问题而不使用像主定理 etc.Like 这样的奇特定理

不过用户可以按照自己喜欢的方式回答，我会尽量理解。

Answer 1

在"layman terms"中可以得到较大系数的依赖：

 T(n) = T(n/2) + T(n/2) + O(1)

为 n=2^k 构建调用树，看到最后一层树包含 2^k 项，更高层 2^k-1 项，下一层 2^k-2 等等。数列之和（等比级数）

2^k + 2^k-1 + 2^k-2 + ... + 1 = 2^(k+1) = 2*n

所以这种依赖的复杂度也是线性的。

现在获得较小（零）第二个系数的相关性：

 T(n) = T(n/2) + O(1)

并确保线性复杂度。

似乎很明显，所讨论的递归复杂性介于这些更简单示例的复杂性之间，并且是线性的。

在一般情况下，复杂分支的重复可以用 Aktra-Bazzi method (more general approach than Master theorem)

解决

我假设依赖是

T(n) = T(n/2) + T(n/3) + O(1)

在这种情况下 g=1，要找到 p 我们应该用数值求解

(1/2)^p + (1/3)^p = 1

得到p~0.79，然后积分

T(x) = Theta(x^0.79 * (1 + Int[1..x]((1/u^0.79)*du))) = 
       Theta(x^0.79 * (1 + 4.8*x^0.21 - 4.8) =  
       Theta(x^0.79 + 4.8*x) =  
       Theta(x)

所以复杂度是线性的

计算递归关系的时间复杂度 f(n) = f(n/2) + f(n/3)

Calculate the time complexity of recurrence relation f(n) = f(n/2) + f(n/3)

algorithm

time-complexity

recurrence