这段代码的时间复杂度是多少？
int i = 1;
while (i < n/2)
{
i = i * 2;
int j = i;
while (j > 1)
--j;
}
int i = 1;
while (i < n/2)
{
i = i * 2;
int j = i;
while (j > 1)
--j;
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
O(n)：外循环在每次迭代中运行
logn次：i=1,2,4,8,...n/4（入口值）内部循环运行
2*i次（入口值）所以总的来说，你得到：
2+4+8+...+n/2 = n-2 = O(n)O(n):outer loop runs
logntimes, in each iteration: i=1,2,4,8,...n/4 (entrance values)inner loops runs
2*itimes (entrance values)so at overall you get:
2+4+8+...+n/2 = n-2 = O(n)内部循环在第一次迭代时执行两次，然后四次，然后八次，依此类推。
因此，您需要弄清楚总和在哪里终止：
然后计算出如何计算它（线索：几何级数）。
The inner loop executes twice on the first iteration, then four times, then eight times, etc.
So you need to figure out where the sum terminates:
and then work out how to evaluate it (clue: geometric series).