※ 引述《shortid (我是短哀低)》之铭言： : 大家好 : 这里有一个观念想要请教各位版友 : 书本上说0-1背包问题的复杂度是O(nW)=O(n2^m) : m=lg W : 这部分的解释真的看不太懂，希望可以请教各位 : 我的理解是因为W其实仅需lg W bits即可，而却需要处理W时间，所以相当於输入m，却花了2^m等级的时间 : 然而如果是这样我觉得不懂的是那为什麽其他的问题没有这个状况呢？ : 其他问题我input n不也是只需要lg n bits就可以存了吗？那为什麽其他问题不会有这个结论？ : 我猜我是对这个这个理解有误，希望版友可以解惑，谢谢！！ 要了解这问题，你要知道电脑是怎麽接受输入的，以 knapsack 问题来说， 输入有 n 个物品，第 i 个物品有重量 wi 和价值 vi 。 除此之外还有一个重量限制 W ，那在电脑之中需要多少 bit 来表示这些输入？ 假设输入是下面的形式（当然也可能有其他形式，只是应该不会影响结果） n,(w1,v1),(w2,v2), ...,(wn,vn),W 要表示 W 的值， W 至少要使用 m = lg W bits 。又因为时间复杂度是 O(nW)， 所以时间复杂度可以表示成O(n2^m)。 这情况常常出现在输入是一个数值的情况。 另一个常见的例子是 factorization : 给定一个正整数 N > 1 ，把 N 作因式分解。 暴力法就是从 i = 2 ~ sqrt N 一个一个去试除来作因式分解。 时间复杂度是 O(sqrt(N)) ，但是基於相同的原因，这方法不是多项式时间的。 至今，除了量子电脑之外，还没有多项式时间的方法来作因式分解。 那为什麽其他问题没有这情况？ 令除了 W 之外的输入长度为 N bits 。 时间复杂度是要讨论 worst case ，输入当然可以使用 N bits 来只表示 一个物品，也就是 w1 或是 v1 特别的长。但是这样并不会是 worst case ， 因为输入的物件变少了，问题就简单了。 所以 worst case 情况是用 N bits 表示越多物品越好。 因为每一个物品至少也要 O(1) bits 来表示，物品个数 n 就会是 O(N) 了。 此时输入长度 N 也会是 O(n) 。 所以在这个时候就不用考虑物品输入的长度，单纯考虑个数就可以了，因为 O(NW) 和 O(nW) 是一样的意思。 同理，排序问题也只需要考虑输入的个数，而不是输入的长度，因为个数和 长度是等价的。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 24.23.200.172 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1476022105.A.C89.html