作者NTUmaki (西木野真姬)
看板Grad-ProbAsk
标题[理工] pseudo polynomial time
时间Sun Sep 6 15:15:36 2020
版上两篇文章看过了，但有些还是不懂、想确认
我目前理解是这样：
0/1 knapsack problem 复杂度 O(nW)
n是物品数量（阵列有多少个‘’元素‘）
W就是一个数值（input 只会看到一个东西）
但数值跟物品数量都是人的定义，对电脑来说最後都是开了nW的二维阵列，算了nW格的东西。所以其实数值、数量对电脑程式来说没差吧？
所以不太懂要取 m=lgW 然後说复杂度是O(n2^m) 的理由
目前我是这样理解：
因为复杂度理论也是人定义的，所以当初我们要求的input 必须是一个可以数有多少个的东西，以此题来说，input就会真的出现n+1数字（n个价格、1个重量）
W我们没办法说他 size 是1，要找一个会随着W变大而增长的东西当input size，所以取 bit 数当他的size
这边再提一个疑问，如果我是取他有几位数可以吗？（取log 10为底，反正出来的是exponential）
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.247.233.249 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1599376538.A.02E.html
1F：推 aarzbrv: 「我是取他有几位数可以吗？」的回答，就是您所理解到的 09/06 15:59
2F：→ aarzbrv: 「所以取bit 数当他的size」。 09/06 16:00
3F：推 aarzbrv: 会不会是因为还没发明电脑的社会习惯用log 10，发明後用 09/06 16:05
4F：→ aarzbrv: log 2，造成您的困惑呢？ 09/06 16:05
5F：→ NTUmaki: 不算困扰，只是想说关键应该是要把W的size量化成 随着W这 09/06 16:11
6F：→ NTUmaki: 个数字越大，他的size也要越大，所以取他有几位也对吧 09/06 16:11
7F：推 aarzbrv: 或是「取他有几位(元)」，您是否认同在下多加一个字呢？ 09/06 16:21
8F：→ NTUmaki: 原本的我同意啊，只是我想说取几位表达趋势 也是exponent 09/06 16:22
9F：→ NTUmaki: ial 09/06 16:22
10F：推 aarzbrv: 您目前的主文与推文，在下如果没会错意的话，都同意； 09/06 16:27
11F：→ aarzbrv: 希望在下的推文没有误导您的地方，抱歉！ 09/06 16:28
12F：→ NTUmaki: 不会不会 感谢回覆 09/06 20:54
13F：推 FRAXIS: 主要是执行时间跟 W 有关，所以才要讨论 bit。 09/06 22:20
14F：→ FRAXIS: 像是 comparison-based 的 sorting 都是假设 comparison 09/06 22:20
15F：→ FRAXIS: 是 O(1) 时间 与 bit 无关，所以就不用讨论 bit。 09/06 22:20
16F：→ FRAXIS: 但是你也可以定义 comparison 跟 bit 长度有关的计算模型 09/06 22:21
17F：→ FRAXIS: 只是教科书上不太会这样介绍.. 09/06 22:21
好像也是...理论上数字越大要比越久
※ 编辑: NTUmaki (27.247.233.249 台湾), 09/07/2020 20:14:19