作者sooge (喜歡平井桃)
看板Grad-ProbAsk
標題[理工] 資結 時間複雜度
時間Fri Oct 12 22:39:28 2018
https://i.imgur.com/ZYTZ4ya.jpg
請問這題要如何下手 題目看不太懂....
答案就只給一個O(n^2)而已
拜託了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.105.145.196
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1539355170.A.3BB.html
1F：推 tataTangQQ: 一個loop call funtion，function裡也有一個loop10/12 23:38
謝謝你 有看懂了
2F：推 befdawn: 後面還有題目嗎？10/12 23:48
後面剩一個右大括號而已
3F：推 skyHuan: compute_value()副程式是O(k)10/13 00:22
4F：→ skyHuan: 主程式迴圈i從1開始跑到n10/13 00:23
5F：→ skyHuan: i小於1000的時候是O(1)10/13 00:23
6F：→ skyHuan: i很大的時候(超過1000)就是O(i)10/13 00:23
7F：→ skyHuan: 複雜度=1+1+...+1+1000+1001+1002+...+n=O(n^2)10/13 00:23
可是題目上是寫n<1000，不是i<1000
是題目有錯嗎
※ 編輯: sooge (125.231.41.246), 10/13/2018 02:11:54
8F：推 skyHuan: 喔喔喔我看錯題目，那還是一樣在n很大的時候迴圈O(n)跑n10/13 07:47
9F：→ skyHuan: 次，所以O(n^2)10/13 07:47
10F：推 skyHuan: 複雜度是討論n很大的時候。還有這題程式s沒設初值跑應該10/13 07:49
11F：→ skyHuan: 會出錯雖然跟這題無關XD10/13 07:49
另外我想問value=value+(i*k)這個式子
最後答案不是要變成
（0+1+.......k-1)*k=[(k-1)*k/2]*k嗎
然後代回n應該是O(n^3)才對
為什麼會是O(n^2)
※ 編輯: sooge (125.231.41.246), 10/13/2018 10:32:59
12F：→ skyHuan: value=value+(i*k)這個式子只要O(1)，迴圈跑k次所以compu 10/13 10:47
13F：→ skyHuan: te_value()整個副程式呼叫一次是O(k)，複雜度是看input d10/13 10:47
14F：→ skyHuan: ata大小不是看算出來的值 10/13 10:47
不知道我有沒有理解錯誤 所以value=value+(i*k)可以直接看成value++的意思嗎，因為
我們主要是要看它跑了幾次迴圈不是要看它算出來的值
※ 編輯: sooge (120.105.145.168), 10/13/2018 11:11:57
15F：推 skyHuan: 對啊今天如果有一個程式 10/13 11:25
16F：→ skyHuan: int test(int k){ return k*k; } 10/13 11:25
17F：→ skyHuan: 複雜度也是O(1)不是k^2 他只做了一次乘法 10/13 11:25
懂了 太謝謝你了!! 感謝
※ 編輯: sooge (120.105.145.153), 10/13/2018 11:33:32
18F：推 befdawn: 請問s大(可惜這邊不能直接tag哈哈)，複雜度跟 input da 10/13 14:16
19F：→ befdawn: ta 大小有關，是指 input 值大小嗎？(這樣是算 bits？) 10/13 14:16
20F：→ skyHuan: 我說錯了應該要說資料量大小影響到執行"次數"，比如資料 10/13 14:48
21F：→ skyHuan: 量是n，迴圈跑到n，資料量就有影響到複雜度，像上面test( 10/13 14:48
22F：→ skyHuan: )函式如果只是算數"值"就不會影響複雜度 10/13 14:48
23F：→ skyHuan: int test(int k){ return k*k; } => O(1) 10/13 14:52
24F：→ skyHuan: int test(int k){ 10/13 14:52
25F：→ skyHuan: for(i=0;i<k;i++) printf("hello!"); } => O(k) 10/13 14:52
26F：推 befdawn: 了解，謝謝s大解說 10/13 15:10