分析 while 循环
考虑嵌套循环：
for i from 1 to n
k=i;
while(k>0)
do c operations;
k=floor[k/2];
end while
end for
计算操作数 我需要首先知道 while 循环中有多少次迭代，我认为（可能是错误的）： k=i,k=下限[1/2*i],k=下限[1/4]....k=下限[(1/2)^j*i],k=1。我知道最后一个 k 永远是 1 对吗？ while循环内的操作次数是j+1？我不知道如何解决j。 有人可以帮忙吗？
consider a nested loop:
for i from 1 to n
k=i;
while(k>0)
do c operations;
k=floor[k/2];
end while
end for
to compute num of operations
I need to know how many iterations in the while loop first, I figured that(probably wrong):
k=i,k=floor[1/2*i],k=floor[1/4]....k=floor[(1/2)^j*i],k=1. I know the last k will always be 1 right? and the num of operation within the while loop is j+1? and I don't know how to solve j.
Can someone help?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
while 循环循环 log(i) 次。因此，在 for i 循环的一次迭代中，完成了 c * log(i) 操作。所以总共：
c*log(1) + c*log(2) + c*log(3) + ... + c*log(n)
如果您需要渐近运行时：那就是 O(n log ( n))。
while loop loops for log(i) times. so inside one iteration of the for i loop, c * log(i) operations are done. so in total:
c*log(1) + c*log(2) + c*log(3) + ... + c*log(n)
In case you need the asymptotic runtime: that is O(n log (n)).