特定递归函数的增长顺序

以下函数的增长顺序是什么？

    static int counter = 0;

    static void Example(int n)
    {
        if (n == 1) return;

        for (int i = 0; i < n; i++)
        {
            counter++;
        }

        Example(n / 2);
    }

为了解决这个问题，我做了以下工作：

我首先摆脱了内部 for 循环，最终得到：

    static void Example(int n)
    {
        if (n == 1) return;            

        counter++;

        Example(n / 2);
    }

通过分析，我能够看出该方法的增长顺序是 n 的以 2 为底的对数。

所以我认为最终的答案将是对数基数 2 乘以其他值。我怎样才能弄清楚？

让我们看看原始函数和修改后的函数。在原始函数中，您完成了以下工作量：

• 基本情况检查的工作量恒定。
• O(n) 计算数字。
• 递归调用一半大小所需的工作。

我们可以将其表示为递归关系：

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

让我们看看这是什么样子的。我们可以通过注意到这一点来开始扩展它

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

= n + (n / 2 + T(n / 4)

= n + n/2 + T(n / 4)

= n + n/2 + (n / 4 + T(n / 8))

= n + n/2 + n/4 + T(n / 8)

我们可以开始在这里看到一种模式。如果我们将 T(n / 2) 位展开 k 次，我们得到

T(n) = n + n/2 + n/4 + ... + n/2^k + T(n/2^k)

Eventually, this stops when n / 2^k = 1. When this happens, we have

T(n) = n + n/2 + n/4 + n/8 + ... + 1

这评估什么？有趣的是，这个和等于 2n + 1，因为和 n + n/2 + n/4 + n/8 + ... = 2n。因此，第一个函数的复杂度为 O(n)。我们也可以通过使用以下方法得出这个结论主定理 http://en.wikipedia.org/wiki/Master_theorem，但看到这种方法也很有趣。

现在让我们看看新功能。这个有

• 基本情况检查的工作量恒定。
• 递归调用一半大小所需的工作。

我们可以将这个递归写成

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

使用与之前相同的技巧，让我们展开 T(n)：

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

= 1 + 1 + T(n/4)

= 1 + 1 + 1 + T(n/8)

更一般地，展开 k 次后，我们得到

T(n) = k + T(n / 2^k)

This stops when n / 2^k = 1, which happens when k = log₂ n (that is, lg n). In this case, we get that

T(n) = lg n + T(1) = lg n + 1

所以在这种情况下 T(n) = O(log n)。

希望这可以帮助！