伪多项式算法 - 我的理解正确吗？

Question

在Phrudhvi对于这个问题的优雅回答中（什么是伪多项式时间？它与多项式时间有何不同？），除了许多其他重要观点之外，他指出，在时间复杂度的实际正式定义下，他们的示例算法的时间复杂度是指数级的。

我理解了答案中的一切，除了这一点。在答案中，他的示例算法是O(n^4)。然后，他说时间复杂度的正式定义基于表示n所需的位数。因此，我希望他会说时间复杂度是O(x)，其中x是位数。但是，他却说它是O(2^4x)。

我有一个关于为什么我感到困惑以及我认为实际上正在发生的事情的想法。你能告诉我现在我是否正确吗？

这就是我认为自己感到困惑的原因：当 Phrudhvi 正式地说时间复杂度（TC）是基于用于表示输入的位数时，我以为他的意思是解决问题所需的时间每位都是多项式的，也就是人们通常认为 TC 关于 n 的含义，但现在每一位都是线性的。

然而，我现在假设他的意思是正确的，即：即使在时间复杂度的正式定义中，他的示例和算法所需的时间确实基于输入大小 n，并且在他的示例中为 O(n^4)。然而，n 的大小随着 x 的增加呈指数级增长。

这两种时间复杂度的表达都是准确的 - 但由于时间复杂度的正式定义希望将所需时间 O(n^4) 表达为 x 的函数，并且 n 随 x 的增加呈指数级增长，因此在 x 方面，正式的 TC 是 O(2^4x)。

这样对吗？非常感谢！

- TheRealPaulMcCartney

Answer 1

根据对数的属性，可以得出O(2^4x)公式：

• O(number_of_bits) = O(log₂n)，其中n是输入数字
• O(2^{number_of_bits}) = O(n)，根据对数的定义
• 将两边都提升到4次幂可得O(2^{4*number_of_bits}) = O(n⁴)

混淆的源头在于用n标记候选素数的值，然后在解释的其余部分中使用O(n⁴)。更好的方法是从n开始，它是表示候选素数p所需的位数。有了n位，p的值受到2ⁿ的限制。如果算法是O(p⁴)，通过简单地重新标记，可以获得结果O(2^4*n)。

请注意，OP估计计算n mod i的复杂度为O(n³)实际上是保守的。它应该是O((log₂n)³)，因为mod的复杂度取决于表示数字所需的位数，而不是数字本身。但这并不改变答案的有效性。

- Sergey Kalinichenko

---

谢谢，但是这并没有完全解决我的困惑。我明白了数学流程，但不确定为什么你要这样做才能得到O(n^4)？起初，我认为Phrudhvi试图表达的语句“以n为基础所需时间的长度是O(n^4)”是不准确的，并且它实际上是O(log n)或等价的O(bits)。但现在我意识到这个语句“以n为基础所需时间的长度是O(n^4)”确实是正确的，但正式术语“时间复杂度”只是用位来表达同样的数量。这个算法的复杂度是O(2 ^ 4 bits)（数学流程），因此其时间复杂度是O(2 ^ 4 )？这是对的吗？谢谢。 - TheRealPaulMcCartney

@TheRealPaulMcCartney 对于任何固定位数的数字，比如16、32或64位，运行时间受到O(2^416)或O(2^432)等的限制，这是一个常数（我应该补充说是一个大常数，但仍然是一个常数）。因此，对于32位整数，算法的运行时间为O(1)，这当然是不有趣的。只有当您不固定位数时，问题才变得有趣——例如使用某些大整数库。现在，由于表示“p”所需的位数（或字节）是可变的，因此问题在“n”方面呈指数级增长。 - Sergey Kalinichenko

Answer 2

如果我正确理解了你的问题，那么你的困惑可以很容易地得到澄清。算法的TC是根据输入的编码长度来定义的。请仔细理解每个突出显示的术语。最好的方法是始终想象输入写在图灵机的纸带上。如果我们有一个算法，它以数字n作为输入，并使用循环计算第n个三角形数（即输出1 + 2 + 3 + ... + n），那么很容易说算法是线性的，因为它需要n步。这在n的意义上是正确的，但这并不告诉我们算法的TC，因为TC是根据数字n的编码而不是n本身来定义的。习惯上用<n>表示n的编码。例如，4的可能编码如下：

       _ _ _
<4> = |1|0|0|
       ¯ ¯ ¯  
       _ _
<4> = |1|1|
       ¯ ¯  
       _
<4> = |4|
       ¯  
       _ _ _ _
<4> = |x|x|x|x|
       ¯ ¯ ¯ ¯  
       _
<4> = |A| 
       ¯

前三个例子只是位置制数（二进制、三进制、十进制）。 第四个例子是一个退化的编码（它是一元的）。 最后一个例子是一种自定义编码，其中每个n都有来自编码字母表的特定符号。

虽然编码的概念似乎微不足道，但需要时间消化。 您可能想要检查：numeral。

如果我们采用二进制编码，那么数字n的编码长度约为log2(n)。 上述算法的TC为n = 2^l。 因此，它的TC是指数级的。

如果我们选择十进制编码呢？ TC将会是10^l。 乍一看，算法可能没有确定的TC，但实际上TC取决于计算模型，包括编码。

我们通常假设在一个模型中，算术运算只需要一步。
例如，在图灵机上对两个数字求和需要O(l)，而在更高级别的模型上，它被惯例性地变为O(1)。
不幸的是，这些假设并不总是明确说明。

尽管如此，在渐进地使用大O符号时，改变编码的基数只会将其长度以一个常数因子进行变化，我们并不会受到太多困扰。
一般来说，如果一个编码A可以在多项式时间内转换成另一个编码B，我们不必指定我们是使用A还是B，因为即使将编码转换与算法链接起来，我们仍然拥有一个多项式算法（如果原始算法是这样的话）。
相关内容：多项式时间规约。

现在，应该很容易理解维基百科给出的伪多项式时间定义了。

在计算复杂性理论中，如果数值算法的运行时间是输入数值值的多项式，则其运行时间为伪多项式时间。

- Margaret Bloom