Über die Pseudo-Polynom-Komplexität des KnapSack 0/1-Problems
Ich habe gelesen Warum ist der dynamische Programmieralgorithmus des Rucksackproblems nicht polynomisch? und andere verwandte Fragen, daher ist dies kein Duplikat, sondern nur ein verwandtes Fragenpaar, um einige Zweifel auszuräumen.
Eine Frage, die häufig bei der Erörterung der Komplexität der dynamischen Programmierlösung für das KS-Problem auftaucht, ist etwa ¿Warum$O(n \cdot W)$wird nicht als Polynom betrachtet? .
Die übliche Antwort ist, dass wir uns per Definition mit der Laufzeit eines Algorithmus als Funktion der Größe der Eingabe befassen . Es ist also richtig zu sagen, dass die Laufzeit durch ein Polynom im Wert von begrenzt ist$W$ist nicht polynomisch in der Größe von$W$, denn tatsächlich haben wir was $O(n \cdot 2^W)$.
Hier können wir auch fragen: Warum nicht?$O(2^n \cdot 2^W)$? dh aus der gleichen Begründung$n$sollte auch in der Länge der Eingabe exponentiell sein. Aber der "Trick" ist, dass es scheint$n$wird normalerweise (immer?) überhaupt nicht als Teil der Eingabe betrachtet. Stattdessen ist die Eingabe (gemäß Konvention, denke ich) nur eine Liste von$n$ Gewichte, eine Liste von $n$ Werte und Kapazität $W$. In der Tat brauchen wir nicht$n$ selbst in der Eingabe.
Fragen:
- Angenommen, wir haben $n$selbst in der Eingabe, da mich nichts davon abhält, es auf diese Weise zu tun. Der Algorithmus durchläuft eine Schleife von$0$ zu $n$ auf die gleiche Weise schleift es ab $0$ zu $W$. Nun ist es richtig zu sagen, dass die Laufzeit ist$O(2^n \cdot 2^W)$ ?.
- Aber wenn (1) richtig ist, denke ich nicht, dass dieser Algorithmus mit $n$in der Eingabe haben das gleiche asymptotische Verhalten wie die gemeinsame. Wie$O(2^n \cdot 2^W)=O(2^{n+W})$ vergleichen mit $O(n \cdot 2^W)$ ?.
- Betrachten Sie den üblichen naiven rekursiven Algorithmus für das KS 0/1-Problem. Das soll sein$O(2^n)$, weil im schlimmsten Fall zwei rekursive Aufrufe auf $n-1$wird gebraucht. In diesem Fall,$n$ ist eindeutig in der Eingabe, aber wir überlegen $n$als Wert bei der Wiederholungsanalyse. In Anbetracht der früheren Diskussion bin ich versucht zu sagen, dass wir dies tatsächlich getan haben$O(2^{(2^n)})$ Was ist doppelt exponentiell und nicht nur exponentiell ... aber macht das Sinn?
Antworten
Ob $n$ist "in der Eingabe enthalten" oder nicht, ist irrelevant. Es werden keine "Tricks" verwendet, um sich heimlich zu verstecken$n$ von der Eingabe durch implizites Einfügen als Länge einer Liste.
Die Eingabe ist mindestens $n$Bits lang , weil es muss eine Liste aller Werte und Gewichte der Elemente enthalten. Wenn wir die Werte und Gewichte der Elemente nicht als Teil der Eingabe erhalten, wie sollen wir dann das Problem lösen (wenn wir das Gewicht / den Wert einiger Elemente nicht kennen)?
Nun, da wir wissen, dass der Eingang mindestens eine Länge (in Bits) hat $n$, jede Laufzeit des Formulars $n, n^2, n^3,...$ist polynomisch in der Länge der Eingabe .
Die Länge von a (angemessene Darstellung der Eingabe) beträgt jedoch höchstens $O(n\log W)$(vorausgesetzt, die Werte der Elemente liegen in der gleichen Größenordnung wie ihre Gewichte). Für jeden Artikel müssen wir das Gewicht und den Wert angeben, und dies kann mit erfolgen$\log W$ Bits pro Element (durch Angabe der binären Darstellung des Gewichts / Werts).
Wie Yuval bemerkte, $nW$ ist kein Polynom in $n\log W$.
Es spielt keine Rolle, ob wir die Eingabe nur als Listen oder als Listen "zusammen mit" betrachten. $n$. Wenn wir auch einschließen$n$ explizit macht es nur die Eingabe $\log n$etwas länger . Aber da ist die Eingabe schon mindestens$n$ Bits lang, mit $\log n$ zusätzliche Bits machen keinen Unterschied.
Angenommen, es gibt $n$ höchstens ganzzahlige Größengewichte $W$. Wir können jedes Gewicht in codieren$O(\log W)$ Bits, und so ist die gesamte Eingangslänge (in Bits) $O(n\log W)$. Ein Algorithmus ist polynomisch, wenn seine Laufzeit ist$O((n\log W)^C)$ für einige $C$. Dynamische Programmierung läuft in$\Theta(nW)$. Unglücklicherweise,$nW$ kann nicht begrenzt werden durch $O((n\log W)^C)$ für jede Konstante $C$.