Blatt 1 Aufgabe 1

  • Ich bin auf $n^{6}log(n^3 + m^2)$ gekommen.


    Wenn ich die Angabe richtig verstanden habe, müssen wird nur das selbe machen was wir auf Seite 14 im Foliensatz zur zweiten VO machen.


    1. Wenden wir die Reduktion von $A$ auf $B$ an um alle Elemente des Problems $A$ in Elemente des Problems $B$ zu überführen (das dauert $O(n^3 +m^2)$)
    2. Dann lassen wir unseren Algorithmus unser Reduziertes Problem (der $O(n^2 log(n))$ benötigt) lösen
    3. Gesamt benötigen wir dann eine Zeit von $O((n^3 +m^2)^2 * log(n^3 +m^2)) = O(n^{6}log(n^3 + m^2))$


    Zwischenrechnung für Schritt 3:
    $(n^3 +m^2)^{2}log(n^3 +m^2) = $
    $(n^6 + 2n^3 m^2 +m^4) * log(n^3 + m^2) = $
    $n^{6}log(n^3 + m^2) + 2n^{3}log(n^3 + m^2) m^{2}log(n^3 + m^2) +m^{4}log(n^3 + m^2)$

  • Hallo, ich bin das anders angegangen. Die Maximale Anzahl an Kanten in einem Graphen ist ja n*(n-1)/2 = O(n^2)
    dann läuft die Reduktion in O(n^4) ab.
    Das eingesetzt in die Lösung von Problem B ergibt n^8*log(n^4)
    könnte das passen ?

    Edited 3 times, last by wosa ().


  • Sofern mich nicht alles täuscht ist $(n^3 + m^2)^2 * log(n^3 + m^2) = (n^6 + 2n^3*m^2 + m^4) * log(n^3 + m^2)$


  • Das heißt du hast $n^2*log(n^2)$ mit $log(n^3+m^2)$ abgeschätzt?

  • Hallo, ich bin das anders angegangen. Die Maximale Anzahl an Kanten in einem Graphen ist ja n*(n-1)/2 = O(n^2)
    dann läuft die Reduktion in O(n^4) ab.
    Das eingesetzt in die Lösung von Problem B ergibt n^8*log(n^4)
    könnte das passen ?


    Hab's nicht nachgerechnet, aber da mit zwei Variablen so einer Wurscht zusammen kommt, explizit darauf hingewiesen wird, dass n/m Knoten/Kanten sind und wir eh nur eine obere Schranke angeben müssen, halte ich das für den "Trick" nach dem sie gesucht haben.


    Allerdings ist puttyflame's Ansatz ja sicher nicht flasch, eigentlich sogar genauer. Ich würde mich nur nicht trauen, da O(n^6log(n^3+m^2)) herauszuheben. Meine Big-O Künste sind etwas eingerostet, besonders in zwei Variablen. Wie genau kann ich da sicher sein, dass ich die Terme mit m^2 und m^4 streichen kann?