pseudopolynomielle Laufzeit |
| 12.08.2009, 00:04 | Auf diesen Beitrag antworten » |
| informatiker | pseudopolynomielle Laufzeit Hallo Habe mich mit dem Rucksackproblem beschäftigt. Nun verstehe ich nicht, warum der Algorithmus pseudopolynomielle Laufzeit besitzt. Dieser Begriff ist mir neu. Die Erklärung bei Wikipedia verstehe ich nicht. Kann das bitte evtl. jemand erklären? Ich zermater mir echt das Hirn 
|
|
|
|
| 12.08.2009, 12:27 | Auf diesen Beitrag antworten » |
| Thomas | Gibt es spezielle Schritte bei der Wikipedia-Erklärung, die du nicht verstehst? |
| 12.08.2009, 14:38 | Auf diesen Beitrag antworten » |
| informatiker | Der Beispiel-Algorithmus zur Bestimmung von Primzahlen (siehe http://de.wikipedia.org/wiki/Pseudopolynomiell) hat eine Laufzeit von n. Dann wird gesagt, dass die Eingabelänge eine Rolle spielt. Nimmt man die Binärdarstellung von Zahlen, benötigt man ca. log(n) Bits für eine Zahl n. Warum kommt man auf eine exponentielle Laufzeit? Was hat das eine (lineare Laufzeit n) mit dem anderen (Logarithmus) zu tun? Ist die algorithmische Berechnung des Logarithmus gemeint? Dieser hat ja exponentielle Laufzeit, wenn man eine Potenzreihe zugrunde legt. |
| 12.08.2009, 22:44 | Auf diesen Beitrag antworten » |
| Thomas | Polynomiell (http://de.wikipedia.org/wiki/Polynomialzeit) hast du verstanden? |
| Anzeige | |
|
|
|
| 13.08.2009, 15:33 | Auf diesen Beitrag antworten » |
| informatiker | Polynomielle und exponentielle Laufzeit sind bekannt. |
| 14.08.2009, 01:10 | Auf diesen Beitrag antworten » |
| Thomas | Der Knackpunkt liegt im Unterschied zwischen Länge und Wert bei unterschiedlichen Kodierungen, nur bei der unären Kodierung fällt dies zusammen und der pseudopolynomielle wird zum polynomiellen Fall. |
| 14.08.2009, 21:37 | Auf diesen Beitrag antworten » |
| informatiker | Warum kodiert man dann nicht im unären? Hätte man das Problem dadurch nicht gelöst? |
| 15.08.2009, 18:37 | Auf diesen Beitrag antworten » |
| informatiker | Hat sich erledigt. |
|
|
