以下递归算法的时间复杂度是多少？

Question

下面递归算法的复杂度是多少？

void rec(n){
 if(n<=0)
    return;
 else
    rec(n/3)+rec(n/2); 
}

Answer 1

上述程序的时间复杂度为O(2 ^ k)，其中k为递归深度。在这里，2 源于这样一个事实，即在每个递归调用中，我们都会调用另外 2 个递归调用。现在，让我们分析最深的递归深度（k）。

在上图中，每一步除以2的递归路径将需要更长的时间才能达到小于1的值（这是基本情况），因此它将是最深的递归深度。因为，每次我们都将 n 除以 2。要达到小于 1 需要对数步数。虽然我们也把n除以3。将 n 除以 2 将花费更长的时间，因此是最深递归深度的决定因素。详情：

In 1st call, we reduce n by n / 2.
In 2nd call, we reduce n by (n / 2) / 2 = n / 4 = n / 2^2.
Hence, In Kth step, we reduce n by : n / 2^k = 1.
So, n = 2 ^ k.

两边取对数底数2，

log2 n = log2 (2^k)
log2 n = k log2(2)
log2 n = k * 1 [ since, log2(2) is 1 ]

因此，在最深的递归深度中，我们需要 k = log(n) 步才能达到 n = 1，再需要一步才能达到 n <= 0。但是，总体递归深度将介于 log3 n 到 log2 n.

因此，在最坏的情况下，总体时间复杂度为 O(2 ^ log n)。但是，由于我们还将 n 除以 3，因此从顶部到叶节点的所有递归路径深度将与 log n 的深度不同。因此，我们可以得出时间复杂度为 O(2 ^ k)，其中 k 是递归深度。

以下递归算法的时间复杂度是多少？

What will be the time complexity of following recursive algorithm?

algorithm

time-complexity

master-theorem