作者silence0925 (書山壓力大)
看板Grad-ProbAsk
標題[理工] 資結題庫
時間Tue Nov 20 21:44:44 2018
https://i.imgur.com/kieT9XQ.jpg
如圖 答案為什麼不是D 麻煩大大們解惑
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.237.25
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1542721487.A.7CB.html
1F：推 nannnnn: 內層迴圈大概是2i, 譬如說你帶i=4進去，內層會做4+2+1大 11/20 22:45
2F：→ nannnnn: 約為2*4,之後2(1+2+···+n)大概n^2 11/20 22:45
4F：→ skyHuan: 少拍到一行XD 11/20 22:56
6F：→ silence0925: 抱歉s大 我還是不太懂 假如i=4時 goo不是只會跑3次 11/21 17:45
7F：→ silence0925: 嗎 因為j=i=4 -> 2 ->1 三次 為什麼你們會把他們加起 11/21 17:45
8F：→ silence0925: 來 那個數字是j等於多少跟次數沒關係不是嗎 麻煩大大 11/21 17:45
9F：→ silence0925: 解惑 11/21 17:45
11F：推 skyHuan: 因為j的迴圈要跑goo() 11/21 18:14
12F：→ skyHuan: 題目說goo(m)複雜度是O(m) 11/21 18:14
13F：→ skyHuan: j你跑的4 -> 2 -> 1要把他都加起來 11/21 18:14
14F：→ skyHuan: 大概就是1+2+2^2+... 共加log i次 11/21 18:14
15F：推 skyHuan: goo()的部分沒有每次都跑到n，有至少一半的不到n，每次 11/21 18:17
16F：→ skyHuan: 都用n算是nlogn會太大 11/21 18:17
17F：推 nannnnn: s大 n的次數 因該是取floor是嗎，另外我是看成每次j的迴 11/21 18:53
18F：→ nannnnn: 圈都會執行i當下丟進來的數值的兩倍，所以可以寫成summa 11/21 18:53
19F：→ nannnnn: tion i從1到n (2i) 11/21 18:53
20F：推 skyHuan: 實際好像是logi取floor再多一次，但我會直接挑好算的數字 11/21 19:32
21F：→ skyHuan: 算，少1多1好像不會影響複雜度XD 11/21 19:32
22F：→ silence0925: 還是不太懂4 2 1為什麼需要加起來 在I=4時 goo指呼叫 11/21 19:42
23F：→ silence0925: 了3次 而不是4+2+1次啊 11/21 19:42
24F：→ silence0925: 抱歉 比較笨想不太懂 11/21 19:45
26F：→ nannnnn: 因為題目有說goo是O(m)假設i為4的那一輪近來，總共會做g 11/21 19:53
27F：→ nannnnn: oo(4),goo(2),goo(1)每次各花O(1),O(2),O(4)的時間， 11/21 19:53
28F：→ nannnnn: 所以i=4的時候總共花了大概c*7,c為常數，以此類推i=5,6, 11/21 19:53
29F：→ nannnnn: 7......加起來 11/21 19:53
30F：→ silence0925: 原來如此 了解了 謝謝兩位大大的解釋 11/21 20:00