僞多項式時間和多項式時間

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，它有明顯的多項式增長。