推 nannnnn: 內層迴圈大概是2i, 譬如說你帶i=4進去，內層會做4+2+1大 11/20 22:45
→ nannnnn: 約為2*4,之後2(1+2+···+n)大概n^2 11/20 22:45
→ skyHuan: 少拍到一行XD 11/20 22:56
→ silence0925: 抱歉s大 我還是不太懂 假如i=4時 goo不是只會跑3次 11/21 17:45
→ silence0925: 嗎 因為j=i=4 -> 2 ->1 三次 為什麼你們會把他們加起 11/21 17:45
→ silence0925: 來 那個數字是j等於多少跟次數沒關係不是嗎 麻煩大大 11/21 17:45
→ silence0925: 解惑 11/21 17:45
推 skyHuan: 因為j的迴圈要跑goo() 11/21 18:14
→ skyHuan: 題目說goo(m)複雜度是O(m) 11/21 18:14
→ skyHuan: j你跑的4 -> 2 -> 1要把他都加起來 11/21 18:14
→ skyHuan: 大概就是1+2+2^2+... 共加log i次 11/21 18:14
推 skyHuan: goo()的部分沒有每次都跑到n，有至少一半的不到n，每次 11/21 18:17
→ skyHuan: 都用n算是nlogn會太大 11/21 18:17
推 nannnnn: s大 n的次數 因該是取floor是嗎，另外我是看成每次j的迴 11/21 18:53
→ nannnnn: 圈都會執行i當下丟進來的數值的兩倍，所以可以寫成summa 11/21 18:53
→ nannnnn: tion i從1到n (2i) 11/21 18:53
推 skyHuan: 實際好像是logi取floor再多一次，但我會直接挑好算的數字 11/21 19:32
→ skyHuan: 算，少1多1好像不會影響複雜度XD 11/21 19:32
→ silence0925: 還是不太懂4 2 1為什麼需要加起來 在I=4時 goo指呼叫 11/21 19:42
→ silence0925: 了3次 而不是4+2+1次啊 11/21 19:42
→ silence0925: 抱歉 比較笨想不太懂 11/21 19:45
→ nannnnn: 因為題目有說goo是O(m)假設i為4的那一輪近來，總共會做g 11/21 19:53
→ nannnnn: oo(4),goo(2),goo(1)每次各花O(1),O(2),O(4)的時間， 11/21 19:53
→ nannnnn: 所以i=4的時候總共花了大概c*7,c為常數，以此類推i=5,6, 11/21 19:53
→ nannnnn: 7......加起來 11/21 19:53
→ silence0925: 原來如此 了解了 謝謝兩位大大的解釋 11/21 20:00