Re: [理工] [資結]-時間複雜度
※ 引述《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
推
10/17 00:02, , 1F
10/17 00:02, 1F
推
10/17 00:21, , 2F
10/17 00:21, 2F
討論串 (同標題文章)