伪多项式算法——我的理解对吗？

Question

在Phrudhvi对这个问题的优雅回答中，什么是伪多项式时间？它与多项式时间有何不同？在许多其他要点中，我们指出，在时间复杂度的真实形式定义下，其示例算法的TC在x中是指数的。

我理解答案中的所有内容，除了这里的这一点。在答案中，他的例子alg是O（n^4）。然后，他指出TC的形式定义是基于表示n所需的位数。因此，我希望他说TC将是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）。

是这样吗？非常感谢！

Answer 1

如果我正确理解你的问题，你的困惑可以很容易很快地消除。

算法的TC根据输入编码的长度定义<请花点时间完全理解所强调的每个术语。

理解这一点的最好方法是总是想象输入写在图灵机器的磁带上<如果我们有一个算法，将数字n作为其输入，并用循环计算第n个三角形数（即，它输出1 2 3…n），那么很容易说该算法是线性的，因为它需要n个步骤。

这在某种意义上是正确的，算法在n中是线性的，但这并没有告诉我们算法的TC，因为TC是根据数字n而不是n本身的编码定义的。

通常用来表示n的编码

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

前三个例子只是位置系统（以2、3、10为底）。
第四个例子是退化编码（一元）的例子。最后一个例子是自定义编码，其中每个n都有来自编码字母表的特定符号。

虽然编码的概念可能看起来微不足道，但sip需要时间<您可能需要选中：数字。

如果我们采用二进制编码，数字n具有编码

如果我们选择十进制编码呢 l ^{<一开始，一个算法似乎很难没有确定的TC，但实际上TC取决于计算模型，包括编码。}

例如，在图灵机上求和两个数字需要O（l），而在更高的模型上习惯上是O（1）。
不幸的是，这些假设并不总是陈述的。

然而，当使用大O符号进行渐进运算时，改变编码基只会改变其长度一个常数，我们对此并没有太大的困扰<一般来说，如果一个编码A可以在多项式时间内转换为另一个编码B，我们不需要指定我们是在使用A还是B，因为即使将编码转换与算法链接，我们仍然有一个多项式算法（如果原始算法是这样的话）<相关：多项式时间缩减。

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

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

Answer 2

O（2^4x）公式可以从对数的属性中导出，如下所示：

• O（位的数量）=O（log_{2n），其中n是输入数}

混淆的来源与用n标记候选素数的值有关，然后在解释的其余部分使用O（n^{4）。更好的解决方法是从表示候选素数p所需的位数开始。对于n位，p的值受2n的约束。如果算法是O（p4），则通过简单的重新标记得到结果O（24*n）。}

请注意，OP估计计算n mod i为O（n3）是非常保守的。它应该是O（（log2n）3），因为mod的复杂性取决于表示数字所需的位数，而不是数字本身。不过，这不会改变其余答案的有效性。