: ┌────────────────────────────────────── : │ 实际上，这个问题最大的症结是： : │ 明明输入的是变数W，但是为什麽不能和以前一样输入n就用n估算，输入a就用a估算 : │ W好好的没事还要变成2^logW : │ 才能下去算复杂度... : └────────────────────────────────────── http://en.wikipedia.org/wiki/Pseudo-polynomial_time 在这页有提到质数检查的问题，我觉得就是一个好例子： 考虑一个数 N ，请问他是不是质数？ 我们可以给出一个简单的演算法： for each integer i, 2 <= i <= sqrt(N) if N Mod i = 0 return false return true 这个演算法的复杂度是 O(N^0.5) 是多项式时间 可是，对这个问题来说，我们关心的并不是 N 变成两倍的话， 运算量会多多少 (Ex: N ~= 10000 和 N ~= 20000) 我们所关心的是，从 N ~= 2^32 变成 N ~= 2^64 会差多少？ 我们所谓的 "不同大小的输入" 指的应该是 N ~= 2^n 中的 n 而不是 N ， 当 n 成长时，函数的执行时间会有什麽变化？ 是 O(2^(n/2)) 或是说加法，在一般的讨论下，加法应该是 O(1) ，可是， 如果讨论加法本身，也就是说，算两个 n bits 的数字的和要多久？ 如果今天 n' = 2n ，又要多久？那就不是 O(1) 了，而是 O(n) 。 回到 0/1 kp ，大部分我们遇到的 W 都不大，而且变动的大多是 n ， 如果，今天的题目是： 给两个数 n, w ，代表的是， 有 n 个物品，重量 0<= W <= 2^w ... 的 0/1 KP 问题，那你应该可以想像， w = 10 和 w = 100 所花的时间会差非常非常多。 --

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