推 afulist:對厚 j=j*j 所以是2*2 4*4...感恩 10/17 00:02
推 nowar100:阿對喔 我還以為是解答錯 囧 謝謝指教 XD 10/17 00:21
※ 引述《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