[理工] 資結 時間複雜度

看板Grad-ProbAsk作者 (喜歡平井桃)時間7年前 (2018/10/12 22:39), 7年前編輯推噓8(8推 0噓 18→)
留言26則, 3人參與, 7年前最新討論串11/12 (看更多)
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
推
10/12 23:38, 7年前 , 1F
一個loop call funtion，function裡也有一個loop
10/12 23:38, 1F
謝謝你 有看懂了
推
10/12 23:48, 7年前 , 2F
後面還有題目嗎？
10/12 23:48, 2F
後面剩一個右大括號而已
推
10/13 00:22, 7年前 , 3F
compute_value()副程式是O(k)
10/13 00:22, 3F
→
10/13 00:23, 7年前 , 4F
主程式迴圈i從1開始跑到n
10/13 00:23, 4F
→
10/13 00:23, 7年前 , 5F
i小於1000的時候是O(1)
10/13 00:23, 5F
→
10/13 00:23, 7年前 , 6F
i很大的時候(超過1000)就是O(i)
10/13 00:23, 6F
→
10/13 00:23, 7年前 , 7F
複雜度=1+1+...+1+1000+1001+1002+...+n=O(n^2)
10/13 00:23, 7F
可是題目上是寫n<1000，不是i<1000 是題目有錯嗎 ※ 編輯: sooge (125.231.41.246), 10/13/2018 02:11:54
推
10/13 07:47, 7年前 , 8F
喔喔喔我看錯題目，那還是一樣在n很大的時候迴圈O(n)跑n
10/13 07:47, 8F
→
10/13 07:47, 7年前 , 9F
次，所以O(n^2)
10/13 07:47, 9F
推
10/13 07:49, 7年前 , 10F
複雜度是討論n很大的時候。還有這題程式s沒設初值跑應該
10/13 07:49, 10F
→
10/13 07:49, 7年前 , 11F
會出錯雖然跟這題無關XD
10/13 07:49, 11F
另外我想問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
→
10/13 10:47, 7年前 , 12F
value=value+(i*k)這個式子只要O(1)，迴圈跑k次所以compu
10/13 10:47, 12F
→
10/13 10:47, 7年前 , 13F
te_value()整個副程式呼叫一次是O(k)，複雜度是看input d
10/13 10:47, 13F
→
10/13 10:47, 7年前 , 14F
ata大小不是看算出來的值
10/13 10:47, 14F
不知道我有沒有理解錯誤 所以value=value+(i*k)可以直接看成value++的意思嗎，因為 我們主要是要看它跑了幾次迴圈不是要看它算出來的值 ※ 編輯: sooge (120.105.145.168), 10/13/2018 11:11:57
推
10/13 11:25, 7年前 , 15F
對啊今天如果有一個程式
10/13 11:25, 15F
→
10/13 11:25, 7年前 , 16F
int test(int k){ return k*k; }
10/13 11:25, 16F
→
10/13 11:25, 7年前 , 17F
複雜度也是O(1)不是k^2 他只做了一次乘法
10/13 11:25, 17F
懂了 太謝謝你了!! 感謝 ※ 編輯: sooge (120.105.145.153), 10/13/2018 11:33:32
推
10/13 14:16, 7年前 , 18F
請問s大(可惜這邊不能直接tag哈哈)，複雜度跟 input da
10/13 14:16, 18F
→
10/13 14:16, 7年前 , 19F
ta 大小有關，是指 input 值大小嗎？(這樣是算 bits？)
10/13 14:16, 19F
→
10/13 14:48, 7年前 , 20F
我說錯了應該要說資料量大小影響到執行"次數"，比如資料
10/13 14:48, 20F
→
10/13 14:48, 7年前 , 21F
量是n，迴圈跑到n，資料量就有影響到複雜度，像上面test(
10/13 14:48, 21F
→
10/13 14:48, 7年前 , 22F
)函式如果只是算數"值"就不會影響複雜度
10/13 14:48, 22F
→
10/13 14:52, 7年前 , 23F
int test(int k){ return k*k; } => O(1)
10/13 14:52, 23F
→
10/13 14:52, 7年前 , 24F
int test(int k){
10/13 14:52, 24F
→
10/13 14:52, 7年前 , 25F
for(i=0;i<k;i++) printf("hello!"); } => O(k)
10/13 14:52, 25F
推
10/13 15:10, 7年前 , 26F
了解，謝謝s大解說
10/13 15:10, 26F
‣ 更多 sooge 的文章
文章代碼(AID): #1RmB8YEx (Grad-ProbAsk)
討論串 (同標題文章)
完整討論串 (本文為第 11 之 12 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共12篇)
‣ 更多 sooge 的文章
文章代碼(AID): #1RmB8YEx (Grad-ProbAsk)