[理工] 資結題庫

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