Was ist Pseudopolynomialzeit? Wie unterscheidet es sich von der Polynomzeit?
Was istPseudopolynomialzeit? Wie unterscheidet es sich von der Polynomzeit? Einige Algorithmen, die in pseudopolynomialer Zeit ablaufen, haben Laufzeiten wie O (nW) (für die0/1 Rucksack Problem) oder O (√n) (fürProzessabteilung); Warum zählt das nicht als Polynomzeit?