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

Question

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

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

- Avenash

---

它是无限的吗？n 怎么会变成负数或零？ - Stranger in the Q

@StrangerintheQ：如果是整数，非常容易（在我所知道的大多数语言中，1/2 会产生零）。如果是浮点数，需要更多的处理；如果是双精度浮点数，则需要更长时间（例如，1/1e1000 通常为零）。唯一可能会出现问题的情况是当您有分子和分母都是可伸缩整数的有理数时（例如 Ruby 的 Rational）。 - Amadan

Answer 1

上述程序的时间复杂度为O(2 ^ k)，其中k是递归深度。这里2来自于每次递归调用时我们都会调用另外两个递归。现在让我们分析一下最深的递归深度(k)。

在上图中，每一步除以2的递归路径需要更长的时间才能达到小于1的值（即基本情况），因此它将是递归的最深层。由于我们每次都将n除以2，所以需要log步骤才能达到小于1。虽然我们也将n除以3，但将n除以2需要更长的时间，因此它是决定递归最深度的决定性因素。详情请参见：

在第一个调用中，我们将n减少n / 2。
在第二个调用中，我们将n减少(n / 2) / 2 = n / 4 = n / 2 ^ 2。
因此，在第k步中，我们将n减少：n / 2 ^ k = 1。
因此，n = 2 ^ k。

对两边取以2为底的对数：

log2 n = log2 (2^k)
log2 n = k log2(2)
log2 n = k * 1 [ 因为log2(2)等于1 ]

因此，在最深的递归深度中，我们需要 k = log(n) 步才能达到 n = 1，并且再走一步就能到达 n <= 0。但是，总的递归深度将在 log3 n 到 log2 n 之间。

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

- BishalG