※ 引述《i78524 (Shulei)》之铭言： : 尽管背包问题的时间复杂度为O(nW)，但它仍然是一个NP完全问题。这是因为W同问题的输 : 入大小并不成线性关系。原因在於问题的输入大小仅仅取决於表达输入所需的比特数。事 : 实上，log W，即表达W所需的比特数，同问题的输入长度成线性关系。 我对时间复杂度理论也不熟 以下是我看了维基百科之後的想法 时间复杂度通常有两种input size (1) 数值的大小（bit数量） (2) 数字的数量（其实可以改为(1)的表示法，因为加减乘除都是多项式时间） bubble sort的时间复杂度 用(2)的表示法是O(n^2) 一个数值有m个bit 两个数字比大小是O(m) 用(1)的表示法是O(n^2 * m) 以m的角度来看是多项式时间 0/1 knapsack的时间复杂度 用(2)+(1)的表示法是O(nw) 一个数值有m个bit 用(1)的表示法是O(n * 2^m) 以m的角度来看是指数时间 不知道这样想法正不正确？ --

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