该方案采用递推公式的时间复杂度 [英] Time complexity of the program using recurrence equation
问题描述
我想找出利用递推公式程序的时间复杂度。 这是...
INT F（INT X）
{
如果（X＆LT; 1）返回1;
否则返回函数f（x-1）+ G（x）的;
}
INT克（INT X）
{
如果（X 2）返回1;
否则返回函数f（x-1）+ G（X / 2）;
}
我写的递推方程，并试图解决它，但它不断获取复杂的
T（N）= T（N-1）+ G（N）+ C
= T（N-2）+ G（N-1）+ G（N）+ C + C
= T（N-3）+ G（N-2）+ G（N-1）+ G（n）的+ C + C + C
= T（N-4）+ G（N-3）+ G（N-2）+ G（N-1）+ G（N）+ C + C + C + C
...........................。
........................ ..
第k个... ..
= KC + G（N）+ G（N-1）+ G（N-3）+ G（N-4）.. ..。 ... + T（N-K）
让我们在第k个输入变为1
然后N-K = 1
K = n-1个
现在，我结束了这个..
T（N）=（N-1）C + G（N）+ G（N-1）+ G（N-2）+ G（N-3）+ ... .. ..克（1）
我不能够进一步解决。 如果不计算的这个方案中函数的调用次数任何方式，可以容易地看出，时间复杂性是指数，但我想用复发它证明。如何才能做到呢？
在ANWER 1，说明是正确的，类似的工作我做到了。
在此code最困难的任务是写它的递推公式。我得出另外一个图，我发现了一些图案，我认为我们可以得到一些帮助的形式这张图可能是什么可能的递推方程。
键，我想出了这个公式，不知道这是否是正确的？？？请帮忙。
T（N）= 2 * T（N-1）+ C * LOGN
好吧，我想我已经能够证明 F（X）=西塔（2 ^ x）（注意，时间复杂度是相同的）。这也证明了 G（x）=西塔（2 ^ x）为 F（X）＆GT; G（X）＆GT; F（X-1）。
首先为大家所指出的，很容易证明 F（X）=欧米茄（2 ^ x）。
现在我们有关系的 F（X）＆LT; = 2 F（X-1）+ F（X / 2）（因为 F（X）＆GT; G（x））
我们将表明，在足够大的 X ，有一定的常数 K＆GT; 0 ，使得
F（X）＆LT; = K * H（x），其中H（X）=（2 + 1 / x）^ X
这意味着 F（X）=西塔（2 ^ x），因为 H（x）=西塔（2 ^ x），它本身的事实， H（X）/ 2 ^ X如下 - ＆GT;开方（五）为x轴＆GT;无限（限Wolfram Alpha的链接）。
现在（警告：重数学，perhap cs.stackexchange或math.stackexchange更适合）
根据 Wolfram Alpha的（点击链接，看看级数接近X =无穷大），
H（X）= EXP（X LN（2）+ 2 + O（1 / X））
再次，根据<一href="http://www.wolframalpha.com/input/?i=%282%20%2b%201/x%29%5Ex%20-%202%2a%282%20%2b%201/%28x-1%29%29%5E%28x-1%29"相对=nofollow> Wolfram Alpha的（点击链接（与上述不同），看到了一系列扩张X =无穷大），我们有
H（X） - 2H（X-1）= 1 / 2X + O（1 / X ^ 2）] EXP（X LN（2）+ 2 + O（1 / X））
等
[H（X） - 2H（X-1）] / H（X / 2） - ＆GT;无限为x - ＆GT;无限
因此，对于足够大的 X （比如
H（X）＆GT; = 2H（X-1）+ H（X / 2）
现在有一些 K （只依赖于→（例如K = F（2L）））这样
F（X）＆LT; = K * H（X）对于所有的x＆LT; = 2L
现在我们开始用（强）感应（可以恢复到自然数，如果你愿意的话）
F（X + 1） - = = 2F（X）+ F（（X + 1）/ 2）
通过归纳，右侧则是
＆LT; = 2 * K * H（X）+ K * H（（X + 1）/ 2）
和我们证明了早些时候
2 * H（X）+ H（（X + 1）/ 2）＆LT; = H（X + 1）
因此 F（X + 1） - = = K * H（X + 1）
I want to find out the time complexity of the program using recurrence equations. That is ..
int f(int x)
{
if(x<1) return 1;
else return f(x-1)+g(x);
}
int g(int x)
{
if(x<2) return 1;
else return f(x-1)+g(x/2);
}
I write its recurrence equation and tried to solve it but it keep on getting complex
T(n) =T(n-1)+g(n)+c
=T(n-2)+g(n-1)+g(n)+c+c
=T(n-3)+g(n-2)+g(n-1)+g(n)+c+c+c
=T(n-4)+g(n-3)+g(n-2)+g(n-1)+g(n)+c+c+c+c
……………………….
……………………..
Kth time …..
=kc+g(n)+g(n-1)+g(n-3)+g(n-4).. .. . … +T(n-k)
Let at kth time input become 1
Then n-k=1
K=n-1
Now i end up with this..
T(n)= (n-1)c+g(n)+g(n-1)+g(n-2)+g(n-3)+….. .. g(1)
I ‘m not able to solve it further. Any way if we count the number of function calls in this program , it can be easily seen that time complexity is exponential but I want proof it using recurrence . how can it be done ?
Explanation in Anwer 1, looks correct , similar work I did.
The most difficult task in this code is to write its recursion equation. I have drawn another diagram , I identified some patterns , I think we can get some help form this diagram what could be the possible recurrence equation.
And I came up with this equation , not sure if it is right ??? Please help.
T(n) = 2*T(n-1) + c * logn
Ok, I think I have been able to prove that f(x) = Theta(2^x) (note that the time complexity is the same). This also proves that g(x) = Theta(2^x) as f(x) > g(x) > f(x-1).
First as everyone noted, it is easy to prove that f(x) = Omega(2^x).
Now we have the relation that f(x) <= 2 f(x-1) + f(x/2) (since f(x) > g(x))
We will show that, for sufficiently large x, there is some constant K > 0 such that
f(x) <= K*H(x), where H(x) = (2 + 1/x)^x
This implies that f(x) = Theta(2^x), as H(x) = Theta(2^x), which itself follows from the fact that H(x)/2^x -> sqrt(e) as x-> infinity (wolfram alpha link of the limit).
Now (warning: heavier math, perhap cs.stackexchange or math.stackexchange is better suited)
according to wolfram alpha (click the link and see series expansion near x = infinity),
H(x) = exp(x ln(2) + 1/2 + O(1/x))
And again, according to wolfram alpha (click the link (different from above) and see the series expansion for x = infinity), we have that
H(x) - 2H(x-1) = [1/2x + O(1/x^2)]exp(x ln(2) + 1/2 + O(1/x))
and so
[H(x) - 2H(x-1)]/H(x/2) -> infinity as x -> infinity
Thus, for sufficiently large x (say x > L) we have the inequality
H(x) >= 2H(x-1) + H(x/2)
Now there is some K (dependent only on L (for instance K = f(2L))) such that
f(x) <= K*H(x) for all x <= 2L
Now we proceed by (strong) induction (you can revert to natural numbers if you want to)
f(x+1) <= 2f(x) + f((x+1)/2)
By induction, the right side is
<= 2*K*H(x) + K*H((x+1)/2)
And we proved earlier that
2*H(x) + H((x+1)/2) <= H(x+1)
Thus f(x+1) <= K * H(x+1)
这篇关于该方案采用递推公式的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
