作者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