一个数据结构的时间复杂度问题

于之剥柚 发布于 2012/08/17 11:26
阅读 486
收藏 1
for(int i=2;i<=n;i*=i)
    for(int j=0;j<i/2;j++)
        foo();

求时间复杂度
加载中
0
少帮主
少帮主
O(n^2) * foo的复杂度
0
中山野鬼
中山野鬼

引用来自“少帮主”的答案

O(n^2) * foo的复杂度
他的i不是累加。你注意一下。
0
adler
adler

O(Sn)*foo的复杂度:

其中Sn=2^0+2^1+2^2+2^4+2^8...的前lg2[lg2(n)]项和

怎么数学变换忘了,不对麻烦指正

少帮主
少帮主
回复 @adler : O(N)
adler
adler
回复 @少帮主 : 刚修改了一下,lgn*lgn类型是不对的;感觉应该是这样
少帮主
少帮主
应该是logn*logn, 两次log后平方可以看成O(1)了 log(log(10^10)) = 1
0
billzheng
billzheng

第一个for复杂度: \Omicron(c^n)\!

第二个for复杂度: \Omicron(n)\!

 

0
少帮主
少帮主

引用来自“中山野鬼”的答案

引用来自“少帮主”的答案

O(n^2) * foo的复杂度
他的i不是累加。你注意一下。
 O(n) * O(foo)
0
老陌
老陌

发表下个人愚见。

// 将循环稍做变换:
int x = 0
for(int i=2; i<=n; i*=i) {
	for(int j=0;j<i/2;j++) {
		foo();
	}
	x++;
}
于是可以得到 x 的最大值: x = floor( log 2(log 2(n)) ) 额,这里floor 是向下取整,log 2(n)是以2为底 n的对数 --!

// 再次做变换:
for(int i=0; i <= x; i++) {
	m = 2^(2^i)/2;
	
	for(int j=0; j < m; j++) {
		foo();
	}
}
这样就能计算:( 2^(2^1)+2^(2^2)+……+2^(2^x) )/2 .. 这个怎么归纳.. 还请数学大神帮忙..

0
泡不烂的凉粉
泡不烂的凉粉
是不是O(nlog2n^2);    
0
d
dtn

答案是2^1 + 2^2 + 2^4 + ... + 2^m (m = loglogn, sqrt(n) <= 2^m <= n)

注意,2^m < 2^1 + 2^2 + 2^4 ... + 2^m < 2^1 + 2^2 + 2^3 + 2^4 ... + 2^m < 2^(m+1)

因此答案是 O(2^m),可粗略写为 O(n)

返回顶部
顶部