作者phdch (談感情真苦)
看板C_and_CPP
標題[問題] while迴圈time complexity計算??
時間Sat Feb 28 19:29:43 2009
對於CPP還算是入門者
想請教一下 下面的複雜度怎麼去算?
int i=2;
while(i<n)
{
i=i*i;
x=x+1;
}
非常謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.164.176
1F：推 PRAM:作業自己寫 02/28 20:03
2F：→ phdch:P大 這並不是作業啦 想要自學CPP 遇到瓶頸 02/28 20:08
3F：推 varg:去翻ds 02/28 20:25
4F：推 suhorng:想想看迴圈會跑多少次啊orz ... 02/28 20:56
5F：→ suhorng:應該是log2 n 吧 ? 02/28 20:56
6F：→ MOONRAKER: < log_2 n; for i grows as 2, 4, 16, 256, ... 03/01 00:23
7F：推 yshihyu:應該不是 log2n , log2n 是 2 4 8 16 32 ... 03/01 04:47
8F：推 mantour:i=2^(2^k) , k = 0,1,2,... 03/01 08:25
9F：→ mantour:應該是log_2( log_2 n) 吧 03/01 08:25