时间递归算法的复杂性 [英] Time complexity of a recursive algorithm

问题描述

我如何计算递归算法的时间复杂度？

  INT POW1（INT X，INT N）{
    如果（N == 0）{
        返回1;
    }
    其他{
        返回X * POW1（X，N-1）;
    }
}

INT POW2（INT X，INT N）{
    如果（N == 0）{
        返回1;
    }
    否则，如果（N＆安培; 1）{
        INT p值= POW2（X，（N-1）/ 2）
        返回X * P * P;
    }
    其他 {
        INT p值= POW2（X，N / 2）
        返回P * P;
    }
}
 

解决方案

分析递归函数（或者甚至是评价他们）是一个平凡的任务。 A（在我看来）很好的介绍可以在唐Knuths 具体数学被发现。

然而，让我们来分析一下这些例子现在：

我们定义一个函数，使我们所需要的一个功能的时间。比方说， T（N）表示需要通过的时间战俘（X，N），即函数 N 。

然后，我们可以得出结论，即 T（0）= C ，因为如果我们称之为 POW（X，0），我们要检查是否（ñ== 0 ），然后返回1，可以在一定的时间来完成（因此不断的 ç）。

现在我们考虑另一种情况： N'GT; 0 。在这里，我们得到 T（N）= D + T（N-1）。这是因为我们必须再次检查ñ== 1 ，计算 POW（X，N-1 ，因此（ T（N-1）），并且将结果乘以 X 。检查和乘法可以在一定的时间来完成（恒 D ）的递归计算 POW 需要 T（N-1）。

现在我们可以扩展一词 T（N）：

  T（N）=
D + T（N-1）=
D +（D + T（N-2））=
D + D + T（N-2）=
D + D + D + T（N-3）=
... =
D + D + D + ... + T（1）=
D + D + D + ... + C
 

那么，如何长时间才能，直到我们达到 T（1）？自从我们开始 T（N）和我们减去1中的每一步，它需要 N-1 步骤，以达到 T（N-（N-1））= T（1）。也就是说，在其他的手，意味着，我们得到 N-1 倍恒 D 和 T（1）进行评估，以<​​code> C 。

所以，我们得到：

  T（N）=
...
D + D + D + ... + C =
（N-1）* D + C
 

所以我们得到了 T（N）=（N-1）* D + C 这是O单元（N）。

POW2 可以使用大师定理。既然我们可以假设的算法，时间函数单调递增。所以，现在我们有时间 T（N）需要 POW2（X，N）的计算：

  T（0）= C（因为需要战俘的计算（X，恒定的时间0））
 

为 N'GT; 0 我们得到

如果n是奇数

  /吨（（N-1）/ 2）+ D（D是不变成本）
T（N）=＆LT;
        \ T（N / 2）+ D当n为偶数（d为成本不变）
 

以上可以是简化为：

  T（N）=地板（T（N / 2））+ D＆LT; = T（N / 2）+ D（因为t的单调递增）
 

因此​​，我们获得 T（n）的＆LT; = T（N / 2）+ D ，可使用的主人定理解决T（N）= O（log n）的（参见维基百科的链接，比如二进制搜索，以流行的算法部分应用程序）。

How can I calculate the time complexity of a recursive algorithm?

int pow1(int x,int n) {
    if(n==0){
        return 1;
    }
    else{
        return x * pow1(x, n-1);
    }
}

int pow2(int x,int n) {
    if(n==0){
        return 1;
    }
    else if(n&1){
        int p = pow2(x, (n-1)/2)
        return x * p * p;
    }
    else {
        int p = pow2(x, n/2)
        return p * p;
    }
}

解决方案

Analyzing recursive functions (or even evaluating them) is a nontrivial task. A (in my opinion) good introduction can be found in Don Knuths Concrete Mathematics.

However, let's analyse these examples now:

We define a function that gives us the time needed by a function. Let's say that t(n) denotes the time needed by pow(x,n), i.e. a function of n.

Then we can conclude, that t(0)=c, because if we call pow(x,0), we have to check whether (n==0), and then return 1, which can be done in constant time (hence the constant c).

Now we consider the other case: n>0. Here we obtain t(n) = d + t(n-1). That's because we have again to check n==1, compute pow(x, n-1, hence (t(n-1)), and multiply the result by x. Checking and multiplying can be done in constant time (constant d), the recursive calculation of pow needs t(n-1).

Now we can "expand" the term t(n):

t(n) =
d + t(n-1) = 
d + (d + t(n-2)) = 
d + d + t(n-2) = 
d + d + d + t(n-3) =
... =
d + d + d + ... + t(1) =
d + d + d + ... + c

So, how long does it take until we reach t(1)? Since we start at t(n) and we subtract 1 in each step, it takes n-1 steps to reach t(n-(n-1)) = t(1). That, on the other hands, means, that we get n-1 times the constant d, and t(1) is evaluated to c.

So we obtain:

t(n) =
...
d + d + d + ... + c =
(n-1) * d + c

So we get that t(n)=(n-1) * d + c which is element of O(n).

pow2 can be done using Masters theorem. Since we can assume that time functions for algorithms are monotonically increasing. So now we have the time t(n) needed for the computation of pow2(x,n):

t(0) = c (since constant time needed for computation of pow(x,0))

for n>0 we get

        / t((n-1)/2) + d if n is odd  (d is constant cost)
t(n) = <
        \ t(n/2) + d     if n is even (d is constant cost)

The above can be "simplified" to:

t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)

So we obtain t(n) <= t(n/2) + d, which can be solved using the masters theorem to t(n) = O(log n) (see section Application to Popular Algorithms in the wikipedia link, example "Binary Search").

这篇关于时间递归算法的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！