作者aa871220 (怪人干怪事)
看板Grad-ProbAsk
标题[理工] TSP reduce到 TSP-OPT
时间Sun Sep 13 20:45:30 2020
抱歉这应该算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://webptt.com/cn.aspx?n=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
1F：推 mi981027: 多项式 * 多项式还是多项式时间吧 09/14 07:43
2F：→ mi981027: 且log的成长率低於多项式的成长率 09/14 07:43
3F：→ mi981027: 那就说明 log * 多项式 <= 多项式*多项式，还是被多项 09/14 07:43
4F：→ mi981027: 式时间bound住 09/14 07:43