伪多项式时间和多项式时间

Question

我感到困惑的伪多项式时间比较多项式时间

input(n); 
for (int i=0; i<n;i++){ 
    doStuff; } 

运行时会O(n)但写出数n取x=O(log n)位。因此，如果我们让x是写入输入n所需的位数，则此算法的运行时间实际上是O(2^x)，这不是x中的多项式。 这个结论是否正确？

编辑：看看简单的素数测试。

function isPrime(n): 
    for i from 2 to n - 1: 
    if (n mod i) = 0, return false 
    return true 

运行时将是O(n)。但是请记住，时间复杂度的正式定义会将算法的复杂性作为输入位数的函数。因此，如果我们让x是写入输入n所需的位数，那么算法的运行时间实际上是O（2^x），它不是x中的多项式。编辑2：我得到了你所有的观点，但看看背包问题。 //输入：

// Values (stored in array v) 

// Weights (stored in array w) 

// Number of distinct items (n) 

// Knapsack capacity (W) 


for j from 0 to W do: 

m[0, j] := 0 


for i from 1 to n do: 

for j from 0 to W do: 

    if w[i] > j then: 

     m[i, j] := m[i-1, j] 

    else m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i]) 

如果你们是对的那岂不是背包问题具有运行o(n*W)，因此它具有多项式时间！

Answer 1

由于，
x = ceil(log_2(n))，2^x变得2^log_2(n)，这只不过是n（使用a^log_a(b) = b）。

请记住，只是根据输入变量来分析算法的运行时间，而不是像计算它需要的位那样花哨，因为（在这种情况下，例如）位本身的数量是号码的对数！

Answer 2

亚历克斯每天做64俯卧撑。

和

亚历克斯做日常2^6俯卧撑。

如果上述两行的意思是你也一样，然后O(n)和O(2^x)不要紧:)

O(2^x) 

=> O(2^log_2(n)) 

=> n [as we know x^log_x(y) = y] 

的时间复杂度会谈有关的 复杂的算法函数的正式定义输入的位数。

是的，你说得对。但是，大O分析的思想是关于输入增长的算法的增长率，而不是精确计算我的循环迭代的次数。

至于例如，当n = 32，算法的复杂性是O(2^5)，但与n生长，例如当n = 1048576，复杂度将是O(2^20)。所以，复杂性随着输入增加而增加。

n或2^(log_2(n))都是关于呈现不同数量的相同数量。只要算法的增长率与输入的增长率成线性比例，该算法就是线性的 - 不管我们是否将输入n表示为e^x或log(y)。

编辑

从维基百科

援引O(nW)复杂性并不矛盾的事实，背包 问题是NP完全的，因为W，不像n，不 的长度多项式对问题的投入。 W输入的长度为 该问题与W,log W, 至W本身的位数成正比。

你的前两个片段大约是n，它有明显的多项式增长。