特定递归函数的增长顺序

Question

以下功能的增长顺序是什么？

    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.

所以我认为最后的答案将是log base 2次.我怎么能搞清楚？

Answer 1

让我们看一下原始函数和修改后的函数.在原始功能中,您完成了以下工作量:

• 基础案例检查的工作量不变.
• 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)

最终,当n/2 ^k = 1时停止.当发生这种情况时,我们有

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

这评估的是什么？有趣的是,该和等于2n + 1,因为和n + n/2 + n/4 + n/8 + ... = 2n.因此,该第一函数是O(n).我们也可以通过使用主定理得出这个结论,但看到这种方法也很有意思.

现在让我们来看看新功能.这一个

• 基础案例检查的工作量不变.
• 递归调用一半大小所需的工作.

我们可以把这个重复写为

• 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)

当n/2 ^k = 1 时停止,这发生在k = log ₂ n(即lg n)时.在这种情况下,我们得到了

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

因此在这种情况下T(n)= O(lg n).

希望这可以帮助!