时间戳

首页 > 解决方案 > 计算递归关系的时间复杂度 f(n) = f(n/2) + f(n/3)

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

问题描述

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

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

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

Edit-2 :(在发布第一个答案后）我喜欢 Mbo 给出的答案，但是否可以在不使用任何花哨的定理（如主定理等）的情况下回答这个问题。比如通过制作树等。

但是用户可以自由地回答他们喜欢的方式，我会尽力理解。

标签： algorithmtime-complexityrecurrence

解决方案

在“外行术语”中，您可以获得更大系数的依赖性：

 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 方法解决（比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)

所以复杂度是线性的

推荐阅读