这将是时间的关系T（n）的复杂度=新台币（N-1）+ N [英] what will be time complexity of relation T(n)=nT(n-1)+n

问题描述

这将是时间的关系的复杂性T（N）=新台币（N-1）+ N
在我的PROG像这样

WHAT will be time complexity of relation T(n)=nT(n-1)+n in my prog something like this

f(int n)
{
    c++;
    if(n>0)
        for(i=1;i<=n;i++)
            f(n-1);
}

我参加了一个计数器计数功能多少时间称为
它给出n之间的答案为n！
谢谢。

i took a counter to count how many time function called it gives answer between n to n! thanks.

推荐答案

我们可以列出几个名词

T(0) = 0
T(1) = 1 * 0 + 1
T(2) = 2 * 1 + 2 = 4
T(3) = 3 * 4 + 3 = 15
T(4) = 4 * 15 + 4 = 64
...

我们可以注意到几件事情。首先，函数大于n较快增长;！它开出小于它（N = 0），赶上（以n = 1），超越它（N> = 2）。因此，我们知道，一个下界为n！

We can note a couple of things. First, the function grows more quickly than n!; it starts out smaller than it (at n=0), catches up (at n=1) and surpasses it (at n>=2). So we know that a lower bound is n!.

现在，我们需要的上限。我们可以注意到一件事：T（N）=新台币（N-1）+ N＆LT; NT（N-1）+ NT（N-1）对所有足够大的N（N> = 2，我认为）。但是，我们可以很容易地表明，T（N）=新台币（N-1）是n的递推关系！所以我们知道，T（n）的一个递推关系= NT（N-1）+ NT（N-1 ）=的2nT（N-1）为（n！）（2 ^ N）。我们可以做得更好？

Now, we need the upper bound. We can notice one thing: T(n) = nT(n-1) + n < nT(n-1) + nT(n-1) for all sufficiently large n (n >= 2, I think). But we can easily show that T(n) = nT(n-1) is a recurrence relation for n!, so we know that a recurrence relation for T(n) = nT(n-1) + nT(n-1) = 2nT(n-1) is (n!)(2^n). Can we do better?

我提议，我们可以。我们可以证明，任何C> 0，T（N）=新台币（N-1）+ N＆LT; NT（N-1）+ CNT（n-1个）对于n的足够大的值。我们已经知道，T（N-1）是下面的（N-1）为界;！所以，如果我们把C = N /（N-1）！我们恢复正是我们前pression，我们知道的上限是（C ^ N）（N！）。什么是C的为N趋于无穷大的极限？ 0.什么是假设的最大值[N /（N-1）！] ^ N？

I propose that we can. We can show that for any c > 0, T(n) = nT(n-1) + n < nT(n-1) + cnT(n-1) for sufficiently large values of n. We already know that T(n-1) is bounded below by (n-1)!; so, if we take c = n/(n-1)! we recover exactly our expression and we know that an upper bound is (c^n)(n!). What is the limit of c as n goes to infinity? 0. What is the maximum value assumed by [n/(n-1)!]^n?

好运计算的。 Wolfram Alpha的使得它相当清楚，通过这一功能假定最大值大约是5或6 N〜2.5。假设你是通过说服，有什么外卖？

Good luck computing that. Wolfram Alpha makes it fairly clear that the maximum value assumed by this function is around 5 or 6 for n ~ 2.5. Assuming you are convinced by that, what's the takeaway?

N！ ＆LT; T（n）的＆LT; 〜6N！对于所有的n。 N！是的Theta-必然能为贵复发。

n! < T(n) < ~6n! for all n. n! is the Theta-bound for your recurrence.

这篇关于这将是时间的关系T（n）的复杂度=新台币（N-1）+ N的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！