推 mi981027: 多項式 * 多項式還是多項式時間吧 09/14 07:43
→ mi981027: 且log的成長率低於多項式的成長率 09/14 07:43
→ mi981027: 那就說明 log * 多項式 <= 多項式*多項式，還是被多項 09/14 07:43
→ mi981027: 式時間bound住 09/14 07:43
抱歉這應該算input size與input value
跟時間複雜度關係的問題
這裡還有點搞不懂
https://i.imgur.com/9asCDaA.jpg
我想問的是此題一開始做Binary Search的 bound value不是應該是被 weight 總和卡住嗎
假設 總和為b 則至多要做 log b個iteration
當我input 的graph weight越來越大時
如何保證乘上一個多項式後後仍為多項式時間
-----
Sent from JPTT on my iPhone
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.165.4 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1600001132.A.38C.html
※ 編輯: aa871220 (114.137.165.4 臺灣), 09/13/2020 20:47:27
※ 編輯: aa871220 (114.137.165.4 臺灣), 09/13/2020 20:47:43