Sorry für dumme Frage. Ich kann meine Erinnerung nicht joggen und googeln hat mir nicht geholfen, diese Frage zu beantworten.in einem Graph, ist O (| E | * | V |) Komplexität als Polynom betrachtet oder nicht?
Also im Grunde gegeben ein Graph G (V, E), weiß ich, dass O (| V |^2) oder O (| E |^2 + | V |^2) als polynomische Komplexität betrachtet wird, also ist auch O (| E | * | V |) Polynom? Wenn nicht, welche Art von Komplexität ist das? Ich glaube, es ist auch kein Pseudopolynom.
Eine andere Frage ist: wird O (m * n) auch als Polynom betrachtet, sind m und n die Größen von zwei UNABHÄNGIGEN Eingaben für ein Problem? Ich möchte hier nur das Konzept der Polynomialzeit erklären und wissen wollen, ob O (m * n) einen anderen Namen für seine Art von Komplexität hat.
Oh ja. Boo mich :), wie kann ich das nicht sehen? Die andere Frage ist: ist auch O (m * n) Polynom, gegeben m und n sind die Größen von zwei Eingaben für ein Problem? Ich möchte hier nur das Konzept der Polynomialzeit erklären. – Simo
@Simo, ich verstehe Ihre Follow-up-Frage nicht. Wenn Sie Beispiele für Pseudopolynom für einen Kontrast benötigen, schauen Sie hier: http://stackoverflow.com/questions/4538581/why-is-ist-knapsack-problem-pseudo-polynomial –
der Unterschied ist, dass Pseudo-Polynom-Komplexität in Dieser Fall hängt von der Kapazität (dh der Größe der rechten Hand) ab und dieser Wert könnte täuschend groß sein. –