[理工] 資結 時間複雜度

[sooge (喜歡平井桃)]

https://i.imgur.com/ZYTZ4ya.jpg

請問這題要如何下手 題目看不太懂....

答案就只給一個O(n^2)而已

拜託了

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.105.145.196
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1539355170.A.3BB.html
推 tataTangQQ: 一個loop call funtion，function裡也有一個loop
謝謝你 有看懂了
推 befdawn: 後面還有題目嗎？
後面剩一個右大括號而已
推 skyHuan: compute_value()副程式是O(k)
→ skyHuan: 主程式迴圈i從1開始跑到n
→ skyHuan: i小於1000的時候是O(1)
→ skyHuan: i很大的時候(超過1000)就是O(i)
→ skyHuan: 複雜度=1+1+...+1+1000+1001+1002+...+n=O(n^2)
可是題目上是寫n<1000，不是i<1000
是題目有錯嗎
※ 編輯: sooge (125.231.41.246), 10/13/2018 02:11:54
推 skyHuan: 喔喔喔我看錯題目，那還是一樣在n很大的時候迴圈O(n)跑n
→ skyHuan: 次，所以O(n^2)
推 skyHuan: 複雜度是討論n很大的時候。還有這題程式s沒設初值跑應該
→ skyHuan: 會出錯雖然跟這題無關XD
另外我想問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
→ skyHuan: value=value+(i*k)這個式子只要O(1)，迴圈跑k次所以compu
→ skyHuan: te_value()整個副程式呼叫一次是O(k)，複雜度是看input d
→ skyHuan: ata大小不是看算出來的值
不知道我有沒有理解錯誤 所以value=value+(i*k)可以直接看成value++的意思嗎，因為
我們主要是要看它跑了幾次迴圈不是要看它算出來的值
※ 編輯: sooge (120.105.145.168), 10/13/2018 11:11:57
推 skyHuan: 對啊今天如果有一個程式
→ skyHuan: int test(int k){ return k*k; }
→ skyHuan: 複雜度也是O(1)不是k^2 他只做了一次乘法
懂了 太謝謝你了!! 感謝
※ 編輯: sooge (120.105.145.153), 10/13/2018 11:33:32
推 befdawn: 請問s大(可惜這邊不能直接tag哈哈)，複雜度跟 input da
→ befdawn: ta 大小有關，是指 input 值大小嗎？(這樣是算 bits？)
→ skyHuan: 我說錯了應該要說資料量大小影響到執行"次數"，比如資料
→ skyHuan: 量是n，迴圈跑到n，資料量就有影響到複雜度，像上面test(
→ skyHuan: )函式如果只是算數"值"就不會影響複雜度
→ skyHuan: int test(int k){ return k*k; }  =>  O(1)
→ skyHuan: int test(int k){
→ skyHuan: for(i=0;i<k;i++) printf("hello!"); }  =>  O(k)
推 befdawn: 了解，謝謝s大解說