Sırt çantası problemi dinamik programlama(nW) O karmaşıklığı içinde çözülebileceğini biliyoruz. Ama bu NP-tam bir sorundur diyoruz. Zor anlamak için burada olduğunu hissediyorum.

(n öğeleri sayısıdır. W maksimum ses.)

O(nW) polinom bir zaman gibi görünüyor, ama değil, pseudo-polynomial.hile: Zaman karmaşıklığı bir algoritma olarak işlev gereken zamanı ölçerbit uzunluğukendi girdi. Dinamik programlama çözümü W değeri aslında doğrusal ama W uzunluğu üstel ve önemli olan da bu.

Diğer kaynaklar:

• http://www.cs.ship.edu/~tbriggs/dynamic/index.html
• http://websrv.cs.umt.edu/classes/cs531/index.php/Complexity_of_dynamic_programming_algorithm_for_the_0-1_knapsack_problem_3/27

EDİT

Sırt Çantası problemi için dinamik çözümün zaman karmaşıklığı, temel olarak iç içe geçmiş bir döngü tarafından verilmektedir

// here goes other stuff we don't care about
for (i = 1 to n)
    for (j = 0 to W)
        // here goes other stuff

Böylece, zaman karmaşıklığı açıkça(nW). Bu artış anlamına doğrusal algoritma giriş boyutu nedir? Bu araçları kullanarak giderek daha uzun item dizileri (yani n, n 1, n 2, ...) ve giderek daha uzun W (eğer öyleyse W x biraz uzun, sonra bir adım kullanıyoruz x 1 bit x 2 bit, ...). AmadeğerW x, böylece algoritma ile katlanarak gerçekten polinom değildir büyüyor, ama polinom, bu nedenle adı gibi görünüyor: pseudo-polinom) üstel