时间戳

首页 > 解决方案 > 为什么背包问题的运行时间是 W 的 n 和 2 位数

algorithm - 为什么背包问题的运行时间是 W 的 n 和 2 位数

问题描述

由于这篇文章，我最近开始了解伪多项式的含义。但是，我的一个迫切问题是，为什么背包问题与动态编程一起使用时的运行时间在此处输入图像描述为在此处输入图像描述. 其中 n 是考虑用于背包的物品数量，在此处输入图像描述它是编码 W 所需的位数，在此处输入图像描述是给定 x 位的可能状态（值）的数量。考虑到时间复杂度的正式定义将问题的大小定义为

问题输入的大小是写出该输入所需的位数。

由于权重的位数不是固定的，而是可变的，因此从 0 到 W 乘以值 n 或 的所有可能值最多有在此处输入图像描述总位数在此处输入图像描述。话虽如此，为什么背包的运行时与动态编程配对时的运行时为在此处输入图像描述而不是在此处输入图像描述。我知道，在此处输入图像描述但时间复杂度是指输入的大小为位数。我做了什么假设，或者我遗漏了什么可以纠正这种脱节的知识。

标签： algorithmtime-complexitybig-oknapsack-problem

解决方案

这是与背包输入大小相关的解释。

  • 项数n可以用 O(lg n ) 位表示；
  • n项权重：注意每个项的权重必须≤ W（否则我们可以忽略那些权重大于W的项），我们可以使用 O(lg W ) 位表示每个项的权重，总共 O( n lg W ) 位;
  • n项值：设最大值为V。然后，可以使用 O(lg V ) 位来表示每个项目值，总共 O( n lg V ) 位。

因此，总输入大小为 O(lg n + n (lg W +lg V )) = O( n (lg W +lg V ))。

设b = lg W和v = lg V。那么输入大小是O( n ( b + v ))。现在，请注意，在动态规划解决方案 v 的 O( nW ) 运行时间中，v没有明确显示，因此运行时间为 O( nW ) = O( n2^b )。

推荐阅读