a)
void f(n){
if(n<=1) return;
else{
g(n); //g(n) is O(N^2).
f(n/2);
f(n/2);
}
}
b)
void f(n){
if(n<=1) return;
else{
g(n); //g(n) is O(N).
f(n-1);
f(n-1);
}
}
c)
void f(n){
if(n<=1) return;
else{
g(n); //g(n) is O(N^2).
f(n-1);
f(n-1);
}
}
如何计算上述两个代码片段的O(n)复杂度?
a) 我得到了答案O(n^2),因为每个f(n)递归调用自身两次。由于树的深度是LogN (n/2),整体复杂度为O(n^2),我是否应该忽略g(n)方法,因为它也是N^2的?
b) 由于树的深度为N,并且每个f(n)会递归调用自身两次。由于每个级别需要执行g(n)操作N次,所以我得到的答案是O(N.2^(N))。
c) 和b相同,但g(n)执行了N^2次 - 因此是O(N^2.2^(N))。
这个答案正确吗?
O(2^n)
- 原因在于公式T(n) = 2^n + n.sum(2^i)
的第二项中,n不能被分解为递增的和,即(b)为n + 2.(n - 1) + ... + 2^n
,(c)为n^2 + 2.(n-1)^2 + ... + 2^n
。 - Alexandre Duprieztheta(2^n)
- 不确定如何简化求和?无论如何,我不会太在意得到部分和的精确表达式 - 我只是通过事实来证明sum(2^i.(n-i)) = 2^n.sum((n-i)/2^(n-i)) = 2^n.sum(k/2^k)
,并且它发生了一般术语k/2^k
的系列收敛于一个有限数(称之为c
),由于有限和是递增的,所以sum(k/2^k) <= c
,因此2^n.sum(k/2^k) <= c.2^n
,由于我们可以找到另一个形式为d.2^n
的下界,其中d < c
,因此您获得了theta(2^n)
。 - Alexandre Dupriezg(n)
,使得级数sum(g(n)/2^n)
是有限的,这特别地让我们能够访问任何形式为a1.n^p1.log(n)^q1 + a2.n^p2.log(n)^q2 + ...
的内容,其中a1, a2, ...; p1, p2...; q1, q2...
等均可。 - Alexandre Dupriezsum(n*2^i) + sum(i*2^i)
。第一部分是等比数列,第二部分在维基百科的求和页面中有指数项部分。此外,wolframalpha可以为我们计算它。我建议回答每个人都要读你的评论。谢谢。 - Bonje Fir