特定递归函数的增长顺序 [英] Order of growth of specific recursive function

问题描述

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

What is the order of growth of the following function?

    static int counter = 0;

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

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

        Example(n / 2);
    }

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

In order to solve it I have done the following:

我首先摆脱了内部的for循环，以便最终得到:

I first got rid of the inner for loop in order to end up with:

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

        counter++;

        Example(n / 2);
    }

通过分析，我可以确定该方法的增长顺序是n的对数底2.

By analyzing that I was able to tell that the order of growth of that method was log base 2 of n .

所以我认为最终的答案将是对数乘以2的对数.我该如何解决?

so I am thinking that the final answer will be log base 2 times something else. How can I figure it out?

推荐答案

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

Let's look at both the original and the modified function. In the original function, you have the following amount of work done:

• 用于基本案例检查的工作量恒定.
• O(n)用来计算数字.
• 递归调用所需大小的一半内容.

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

We can express this as a recurrence relation:

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

让我们看看它是什么样子.我们可以通过注意以下内容开始扩展此操作

Let's see what this looks like. We can start expanding this out by noting that

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

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

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

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

We can start to see a pattern here. If we expand out the T(n / 2) bit k times, we get

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

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

最终，这将在n/2 ^k = 1时停止.

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

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

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

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

What does this evaluate to? Interestingly, this sum is equal to 2n + 1, because the sum n + n/2 + n/4 + n/8 + ... = 2n. Consequently, this first function is O(n). We could have also arrived at this conclusion by using the Master Theorem, but it's interesting to see this approach as well.

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

So now let's look at the new function. This one does

• 用于基本案例检查的工作量恒定.
• 递归调用所需大小的一半内容.

我们可以将重复周期写为

We can write this recurrence as

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

使用与以前相同的技巧，让我们扩展T(n):

Using the same trick as before, let's expand out T(n):

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

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

= 1 +1 + T(n/4)

= 1 + 1 + T(n / 4)

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

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

一般来说，扩展k次后，我们得到

More generally, after expanding out k times, we get

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

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

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) = lg n + T(1) = lg n + 1

所以在这种情况下T(n)= O(lg n).

So T(n) = O(lg n) in this case.

希望这会有所帮助！

这篇关于特定递归函数的增长顺序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！