[理工] TSP reduce到 TSP-OPT

看板Grad-ProbAsk作者 (怪人幹怪事)時間5年前 (2020/09/13 20:45), 5年前編輯推噓1(1推 0噓 3→)
留言4則, 1人參與, 5年前最新討論串1/1
抱歉這應該算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
推
09/14 07:43, 5年前 , 1F
多項式 * 多項式還是多項式時間吧
09/14 07:43, 1F
→
09/14 07:43, 5年前 , 2F
且log的成長率低於多項式的成長率
09/14 07:43, 2F
→
09/14 07:43, 5年前 , 3F
那就說明 log * 多項式 <= 多項式*多項式，還是被多項
09/14 07:43, 3F
→
09/14 07:43, 5年前 , 4F
式時間bound住
09/14 07:43, 4F
‣ 更多 aa871220 的文章
文章代碼(AID): #1VNXHiEC (Grad-ProbAsk)