作者maple205 (艾瑞克)
看板Grad-ProbAsk
标题[理工] code执行次数
时间Wed Mar 28 18:55:23 2018
for(a=1; a<=n ; a*=2){
for(b=1; b<=a; b*=2)
c++;
Q: 上述pseudocode的c++执行次数为「?」的多项式？
外层的a从 2^0, 2^1, 2^3...一直做到2^k=n为止，
所以做了k+1次，而k=log(n)。
内层的b成长速率跟a一样，观察下总执行次数是个等差数列：
1+2+3...直到k
= (1+k)*k/2
= (log(n)+log^2(n))/2
所以c++的执行次数是log^2(n)的多项式。
请问我的观念跟方法对吗？怕考试的时候题目变一下我就写错了...
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 101.9.129.25
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1522234525.A.805.html
※ 编辑: maple205 (101.9.129.25), 03/28/2018 18:55:55
1F：推 outofyou: log2^0 + log2^1 + log2^2 + ... + log2^logn 03/28 22:41
2F：→ outofyou: 答案跟你一样，log^2(n) 03/28 22:45