谢谢DJWS及各路高手的帮忙与回响 在这里谢谢大家愿意花时间看我这个无聊的小问题 :) 之前我有寄信去问补教老师 (补教老师真的很好心，肯愿意理我...) 今天回信了，关於这部份我将老师的解释转录给大家参考 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 这个是最confuse的地方. 复杂度是 a function of input size 我做一表给你对照 input input size ------------------------------------------- A[1..n] n (资料笔数) W logW(其bit数) 如果A是一个有n个元诉的Array, 其input size为n 但是如果你输入到演算法的是一整数W, 其input size会以要用几个bit来算 因此若要将 O(nW)表示成a function of input size, 他就会变成exponential. 这部份你若不懂不用深究, 因为考试不会考这个 复杂度就写O(nW) , 但要记得, 0/1KP为NP complete. ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 我现在的解读为： 如果input是A[1..n] 这一类的话，对电脑来说n确实就是最自然的输入量 (可能在电脑机器底层count跑一下电脑就能理解n这个数值是什麽，不费功夫 ) (他真的就是n个东西、数字等...INPUT是n很合理) (所以时间复杂度的输入量就可以很放心的用n去算) 但是如果输入是一个"整数W"，电脑要先把它换成他能理解的2进位数logW 令 logW=m 0/1 背包的时间复杂度写成 O(nW)=O(n2^logw)=O(n2^m) 虽然我们输入的是整数W，但是对电脑而言 "真正" 他看到的 "输入量" 是2^m... 所以O最後是变成成O(n2^m)，而不是表面上的O(nW) 都写成O(n2^m)，他理所当然不是"多项是时间"，是exponential time 而且又被称作 伪多项式时间 在CORMAN的演算法导论在第2章也有一段话和这个问题相关 『对排序问题，最自然的测量量是是输入项目的数目-例如用来排序的阵列大小n。对许多 其他问题来说，例如将两个整数相乘，输入量的最佳测量量是将输入值以二元符号来表 示的位元总数。』 所以对於输入量是一个"整数"了话要换成二进位表示的位元数应该是没有错 之後看了wiki: http://ppt.cc/F0m_ 和DJWS大的想法之後才有这样的想法 (其实我打到这边才发现我的想法应该和DJWS大是一样的) (bubble sort 的那个例子很有趣，还将两个数化成bit比较时考虑进去，好底层啊) (不过一般来说不需要这样吧，都直接当作O(1)) ┌────────────────────────────────────── │ 实际上，这个问题最大的症结是： │ 明明输入的是变数W，但是为什麽不能和以前一样输入n就用n估算，输入a就用a估算 │ W好好的没事还要变成2^logW │ 才能下去算复杂度... └────────────────────────────────────── 以上是我的想法，也谢谢大家的帮忙 谢谢！ (明明不会考...还花好几天想这个，看来今年考试应该也会很坎坷..) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 163.21.235.246