推 outofyou: log2^0 + log2^1 + log2^2 + ... + log2^logn 03/28 22:41
→ outofyou: 答案跟你一樣，log^2(n) 03/28 22:45
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1522234525.A.805.html
※ 編輯: maple205 (101.9.129.25), 03/28/2018 18:55:55