作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [资结]-时间复杂度
时间Fri Oct 16 23:46:18 2009
※ 引述《afulist (亚弗利斯特)》之铭言：
: I.
: x=0,i=1;
: while(i<=n)do{
: j=2;
: i=i+1;
: while(j<=n)do{
: x=x+1;
: j=j*j;
: }
: }
: 我算O(nlogn)答案给O(nloglogn)
因为j每次都会自己乘自己 也就是 2, 2^2, 2^4, 2^8 ...增加
如果n = 2^2^k 那 就会需要跑k次回圈， k = O( lg lg n )
乘上外层的n 就变成 O( n lg lg n )了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50
1F：推 afulist:对厚 j=j*j 所以是2*2 4*4...感恩 10/17 00:02
2F：推 nowar100:阿对喔 我还以为是解答错 囧 谢谢指教 XD 10/17 00:21