[理工] [資結] 時間複雜度

[lightergogo (賴打葛葛)]

(a)for (a=l; a<=n; a++)
       for (b=l;b<=a; b*=2)
            C++;

(b)for (a=l; a<=n; a*=2)
       for (b=l; b<=a; b++)
           C++;

(c)for (a=l; a<=n; a*=2)
       for (b=l; b<=a; b*=2)
           C++;

該怎麼求呢?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.121.128.33
推 flyguava:連兩題99台科題目 XD
推 taitin:O(nlgn) O((lgn)^2) O(lgnlglgn)
推 EntHeEnd:(b)我算 2n-1 (c)我算 (lgn)^2 +lgn...
→ EntHeEnd:(c)還要除以2
推 assassin88:(b)我也算 2n-1 .. (c)lglgn+lgn-6 ..   這這那那XD
→ assassin88:(c) 也補除以二.. EntHeEnd 似乎跟我算的一樣
推 FRAXIS:C應該是O((lg n)^2)
→ assassin88:我打錯.. 我的式子 (3+logn)(logn-2) 是 (lgn)^2 沒錯
→ EntHeEnd:(c)差一點點 邊界問題
→ EntHeEnd:(c)準確一點 好像是 [(lgn+2)lgn]/2