Effizienz zweier Algorithmen



  • Hallo @ all,

    Gegeben seien 2 Algorithmen:
    A(n) = 8\*n\*log_{ 2 }(n)
    B(n)=nnB(n) = n*\sqrt{ n }

    Gesucht ist nun ein n0n_{ 0 } , sodass nn0:\forall n \geq n_{ 0 } : A(n) ist effizienter als B(n).

    Ich verzweifel am Lösen der Gleichung, da ich den Logarithmus nicht aus der Gleichung entfernt bekomme, vllt versuche ich aber auch den falschen Weg (Schnittpunkte bestimmen)...

    mfG
    O-Notation



  • Laß dir einfach mal beide Graphen zeichnen.
    Oder ein anderer Tipp: rechne mal die Werte für 0, 1 und 2 aus.


  • Mod

    Das sind keine Algorithmen. Das sind zwei Ausdrücke.

    Aufgrund deines Nutzernamens gehe ich mal davon aus, dass das wohl die Komplexität der Algorithmen sein soll. Und aufgrund der Fragestellung und der "8" im ersten Ausdruck gehe ich ferner davon aus, dass das wohl die exakte Komplexität sein soll und nicht - wie es üblich wäre - eine Obergrenze und auch nicht "nur" die Proportionalität der Effizienzklasse (wie es ebenfalls üblich wäre).

    Das sind schon einmal eine Menge Annahmen, wobei besonders die letzte doch sehr unüblich ist, aber anders kann ich keinen Sinn in deine Fragestellung bringen.

    Dann musst du
    8\*n\*log_{ 2 }(n) < n*\sqrt{ n }
    lösen für n >= 0. Eine einfache Lösung, auf die du anscheinend noch nicht gekommen bist, ist n = 1, da log(1) = 0. Aber schon bei n = 2 gewinnt wieder die rechte Seite. Jedoch kann man sich durch Plotten der Funktionen klar machen, dass ungefähr ab n = 11500 wieder die linke Seite kleiner wird. Dies analytisch zu lösen ist schwierig, wie du schon gemerkt hast. Genau genommen ist es sogar unmöglich, eine Lösung in geschlossener Form nur mit elementaren Funktionen anzugeben. Man muss stattdessen neue Funktionen einführen, die einfach darüber definiert werden, dass sie Gleichungen von diesem Typ lösen. Die übliche Funktion für Gleichungen vom Typ y = x * e ^ x (und somit auch n * log(n)) zu lösen ist die Lambertsche W-Funktion.
    Damit erhält man nach kurzer Rechnung die beiden Punkte, an denen sich die Funktionen schneiden:
    a) exp(2W0(log(2)/16))\exp(-2*W_0(-\log(2)/16))
    (log ist hier der normale (natürliche) Logarithmus!)
    b) exp(2W1(log(2)/16))\exp(-2*W_{-1}(-\log(2)/16))
    (Siehe Wikipedia, was W0W_0 und W1W_{-1} bedeuten)

    Wenn man die numerischen Entwicklungen (siehe Wikipedia) ansetzt erhält man:
    a) 1.0949 (siehe oben: Bei n = 1 gewinnt A, bei n = 2 gewinnt 😎
    b) 11685.5 (ab hier gewinnt also wieder A)



  • O-Notation schrieb:

    Gesucht ist nun ein n0n_{ 0 } , sodass nn0:\forall n \geq n_{ 0 } : A(n) ist effizienter als B(n).

    Ich verzweifel am Lösen der Gleichung, da ich den Logarithmus nicht aus der Gleichung entfernt bekomme, vllt versuche ich aber auch den falschen Weg (Schnittpunkte bestimmen)...

    Wenn das tatsächlichs so in der Aufgabenbeschreibung steht, musst du doch nur irgend ein n finden, für das das gilt.

    Für n0=2100 ist offensichtlich A(n0)<B(n0), also bist du fertig. Falls du noch zeigen musst, dass der Logarithmus langsamer wächst als die Wurzelfunktion kannst du noch die Ableitungen bestimmen und zeigen, dass die der Wurzelfunktion grösser ist (ab n>2100).



  • taskexploiter schrieb:

    O-Notation schrieb:

    Gesucht ist nun ein n0n_{ 0 } , sodass nn0:\forall n \geq n_{ 0 } : A(n) ist effizienter als B(n).

    Ich verzweifel am Lösen der Gleichung, da ich den Logarithmus nicht aus der Gleichung entfernt bekomme, vllt versuche ich aber auch den falschen Weg (Schnittpunkte bestimmen)...

    Wenn das tatsächlichs so in der Aufgabenbeschreibung steht, musst du doch nur irgend ein n finden, für das das gilt.

    Wieso, da steht doch klipp und klar "für alle n >= n0". Und deshalb reicht das:

    Für n0=2100 ist offensichtlich A(n0)<B(n0), also bist du fertig.

    auch nicht aus.

    Falls du noch zeigen musst, dass der Logarithmus langsamer wächst als die Wurzelfunktion kannst du noch die Ableitungen bestimmen und zeigen, dass die der Wurzelfunktion grösser ist (ab n>2100).

    Das wäre schonmal eine gute Idee.

    Wir wollen 8log2(n)<n8\log_2(n) < \sqrt{n} lösen. Zuerst mal sagt ein Satz aus der Analysis, dass jeder Logarithmus langsamer wächst als jede Potenzfunktion, dh es muss eine Lösung n0 geben. Ich würde dann mal beide Seiten ableiten: Links haben wir 8nln2\frac{8}{n\ln 2}, rechts 12n\frac{1}{2\sqrt{n}}. Die Ungleichung 8nln2<12n\frac{8}{n\ln 2}<\frac{1}{2\sqrt{n}} kann man explizit lösen: Für n>256(ln2)2n > \frac{256}{(\ln 2)^2} ist die linke Ableitung kleiner als die rechte, also wächst die linke Seite langsamer als die rechte. Als nächstes sollte man durch Probieren ein n0 über diesem Punkt suchen, für das die linke Seite kleiner ist als die rechte. Dieses muss nach der anfänglichen Überlegung existieren (kann man mit der Lambertschen W-Funktion machen, aber es ist ja nur irgendein n0 gesucht, nicht das minimale). Jetzt ist man erst fertig.



  • Bashar schrieb:

    taskexploiter schrieb:

    Wenn das tatsächlichs so in der Aufgabenbeschreibung steht, musst du doch nur irgend ein n finden, für das das gilt.

    Wieso, da steht doch klipp und klar "für alle n >= n0". Und deshalb reicht das:

    Für n0=2100 ist offensichtlich A(n0)<B(n0), also bist du fertig.

    auch nicht aus.

    Da steht
    \forall n \geq n_{ 0 } : \operatorname A(n) \text{ ist effizienter als }\operatorname B(n)
    und das bedeutet per Definition, dass die Aussage für n0, n0+1, n0+2, ... gelten muss. Da wird keine Aussage über n<n0 gemacht.



  • taskexploiter schrieb:

    Da steht
    \forall n \geq n_{ 0 } : \operatorname A(n) \text{ ist effizienter als }\operatorname B(n)
    und das bedeutet per Definition, dass die Aussage für n0, n0+1, n0+2, ... gelten muss.

    Genau, also reicht es nicht, sie fuer n0 zu zeigen.

    Da wird keine Aussage über n<n0 gemacht.

    Was hat das mit dem zu tun, was ich geschrieben habe?



  • Was bedeuted das Winkelzeichen in dem Zusammenhang?

    Warum nicht einfach gleichsetzen?

    Danke!



  • Welches Winkelzeichen?



  • \forall - für alle


Log in to reply