Effizienz zweier Algorithmen

Hallo @ all,

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

Gesucht ist nun ein $n_{ 0 }$ , sodass $\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

Th69

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

SeppJ

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(-2*W_0(-\log(2)/16))$
(log ist hier der normale (natürliche) Logarithmus!)
b) $\exp(-2*W_{-1}(-\log(2)/16))$
(Siehe Wikipedia, was $W_0$ und $W_{-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 $n_{ 0 }$ , sodass $\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 n₀=2¹⁰⁰ ist offensichtlich A(n₀)<B(n₀), 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>2¹⁰⁰).

Bashar

taskexploiter schrieb:

O-Notation schrieb:

Gesucht ist nun ein $n_{ 0 }$ , sodass $\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 n₀=2¹⁰⁰ ist offensichtlich A(n₀)<B(n₀), 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>2¹⁰⁰).

Das wäre schonmal eine gute Idee.

Wir wollen $8\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 $\frac{8}{n\ln 2}$ , rechts $\frac{1}{2\sqrt{n}}$ . Die Ungleichung $\frac{8}{n\ln 2}<\frac{1}{2\sqrt{n}}$ kann man explizit lösen: Für $n > \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 n₀=2¹⁰⁰ ist offensichtlich A(n₀)<B(n₀), 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 n₀, n₀+1, n₀+2, ... gelten muss. Da wird keine Aussage über n<n₀ gemacht.

Bashar

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 n₀, n₀+1, n₀+2, ... gelten muss.

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

Da wird keine Aussage über n<n₀ gemacht.

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

Ingeborg

Was bedeuted das Winkelzeichen in dem Zusammenhang?

Warum nicht einfach gleichsetzen?

Danke!

Bashar

Welches Winkelzeichen?

ScottZhang

$\forall$ - für alle