背包问题与排序算法的算法分析

Question

我正在学习算法分析和算法中的设计技术。在研究背包问题时提到，尽管背包是 O(nW)，其中 n 是物品数量，W 是重量。它是非多项式的，如下所述。

The size of input is log(W) bits for the weight (and O(n) for "value" and "weight" arrays).

So, the input size of weight is j = log(W) (and not mere W). So, W = 2ʲ (as binary is used).

The final complexity is O(n * W)

This O(n * W) can be rewritten as O(n * 2^j), which exponential in the size of the input.

根据上述论点，所有算法例如排序算法都是 O(nlogn)，它也变成指数形式 "n"表示为2^j.

我越来越糊涂了。

Answer 1

确定 "polynomial time" 中的算法运行s 是否需要比描述算法的运行ning 时间更严格的 "input size" 定义。例如，下面的算法运行s 在 O(n) 时间内，但不是多项式时间：

count_down(n)
    i = n
    while i > 0 do
        i--

循环迭代 n 次，每次迭代执行 O(1) 工作*，其中 n 是输入数字，因此其时间复杂度为 O(n)。在大多数情况下，说这个算法需要 O(n) 时间是没有问题的。

然而，对于一个算法是否运行s在多项式时间内，我们的意思是它的运行ning时间是否受[=21]的多项式函数限制=]输入大小，通常以位为单位。表示数字 n 所需的位数约为 log2 n，因此这是输入大小，并且 O(n) 不受 log2 n 中多项式的限制。

这不适用于排序算法，因为对于这些算法，n 表示数组的长度而不是数字的大小。仅使用 O(log n) 位来表示长度为 n 的数组是不可能的；它需要 O(n) 位。因此，在这种情况下，运行ning 时间 O(n log n) 或 O(n²) 受输入大小的多项式函数限制，因为输入大小是 n 而不是 log2 n。这意味着此类排序算法在多项式时间内执行运行。

_{*警告：如果就地修改整数，则递减整数需要 O(1) 的摊销时间。在像 Python 这样的语言中，整数是不可变的对象，这需要 O(log n) 时间，因为需要将那么多位复制到一个新对象。}

背包问题与排序算法的算法分析

Algorithm analysis for knapsack problem vs sorting algorithm

algorithm

big-o

analysis