[請益] 關於計算複雜度的問題

看板Master_D作者 (佳慶)時間17年前 (2009/02/09 19:45), 編輯推噓2(2推 0噓 6→)
留言8則, 3人參與, 最新討論串1/1
想請問一下懂演算法的同學 如果說給一個最佳化問題 沒有演算法(使用軟體求解) 要怎麼求這個問題的計算複雜度呢 (computational complexity) 另外關於複雜度方面的問題 要參考哪些書或者是有什麼關鍵字呢 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.217.14
推
02/09 22:21, , 1F
用未知數的大小去測，若有十個未知數，全部花N秒
02/09 22:21, 1F
→
02/09 22:22, , 2F
再丟100個未知數進去，全部花100N秒，推出此程式複雜度N^2
02/09 22:22, 2F
→
02/09 22:23, , 3F
不過這只是一個趨勢，用估計的
02/09 22:23, 3F
→
02/09 23:05, , 4F
謝謝你 幫了大忙 ^^
02/09 23:05, 4F
推
02/10 11:06, , 5F
這個方法會有個問題，就是複雜度可能沒有那麼單純
02/10 11:06, 5F
→
02/10 11:07, , 6F
譬如說如果複雜度是O(loglog n)或是O(α(n))
02/10 11:07, 6F
→
02/10 11:08, , 7F
甚至是output-sensitive algorithm
02/10 11:08, 7F
→
02/10 11:09, , 8F
這些可能都不太容易推測出來，甚至測資不夠還會推錯喔
02/10 11:09, 8F
‣ 更多 rfg 的文章
文章代碼(AID): #19a1Szju (Master_D)