Servus, was ist (n^(log2(n))) für große n (100, 1000, usw.) in O-Notation? Ist das Wachstum polynomiell oder exponentiell? Danke.
Servus, was ist (n^(log2(n))) für große n (100, 1000, usw.) in
O-Notation?
Ist das Wachstum polynomiell oder exponentiell?
Nein zu -> polynomial(da die Exponenten nicht aus natürlichen Zahlen bestehen), jedoch handelt es sich um eine (logaritmische) Exponentialfunktion, deren Wachstumsprozess, sich in der Bestandsgröße immer um denselben Faktor (n) verändert.
Probier es mal selbst (log2(n)) und spar nicht mit den Nullen für (n) und du wirst sehen der Faktor ist irrelevant zu (n*)…man könnte grob sagen das Verhältnis ist linear.
Grob gesagt ist deine O-Notation O(n log n).
Hallo,
Nein zu -> polynomial(da die Exponenten nicht aus natürlichen
Zahlen bestehen)
Seit wann muss denn bei polynomiellem Wachstum irgendeiner Art der Exponent natürlichzahlig sein? O(n^1.5) ist doch auch ein polynomielles Wachstum. Der einzige Grund, der hier gegen polynomielles Wachstum spricht, ist, dass der Exponent nicht konstant ist.
jedoch handelt es sich um eine
(logaritmische) Exponentialfunktion, deren Wachstumsprozess,
sich in der Bestandsgröße immer um denselben Faktor (n)
verändert.
Dem kann ich überhaupt nicht folgen. Wo kommt der Faktor her? Woran wird er multipliziert und was meinst du mit der Bestandsgröße?
Probier es mal selbst (log2(n)) und spar nicht mit den Nullen
für (n) und du wirst sehen der Faktor ist irrelevant zu
(n*)…man könnte grob sagen das Verhältnis ist linear.
Das angegebene Wachstum als linear zu bezeichnen, ist aber schon sehr verwegen. Hast du dir die Funktion mal plotten lassen? Die ist alles andere als linear. Ich würde sie nicht mal als polynomiell oder exponentiell bezeichnen.
Grob gesagt ist deine O-Notation O(n log n).
Nein, ist sie nicht (und falls doch, hätte ich gern einen Beweis dafür). Ich kann hier keine weitere Vereinfachung als O(n^log2 n) sehen.
Nico
1 Like
Hi,
Jetzt wo du es ansprichst sehe ich es erst, hatte das irgendwie gelesen (n*log2(n))…und zeitgleich noch mit einem Exponenten interpretiert (Chaos) -> war dann doch zu spät dafür.
Sorry, mein Fehler -> gut das du es ansprichst!
Gruß XXD
kenne mich auf dem Gebiet auch nicht soo gut aus
aber
O = n^log2(n)
logn(O) = log2(n)
log2(O) / log2(n) = log2(n)
log2(O) = (log2(n))^2
O = 2^((log2(n)^2)
und jetzt?
(log2(n))^2 wächst immer noch langsamer als n
sagt uns das bereits etwas?
bitte überprüfen, ob man folgendermaßen argumentieren kann:
O(n) = n^(log2(n))
wennn die Komplexität polynomial wäre, würde es ein O’(n) = n^k geben, das schneller wächst als O(n)
Also müsste
O’(n) > O(n), für alle n
Eingesetzt:
n^k > n^(log2(n) + k - k)
n^k > n^k * n^(log2(n) - k)
1 > n^(log2(n) - k)
0 > log2(n) - k
k > log2(n)
Es müsste also ein k geben, für das die letzte Ungleichung erfüllt ist, EGAL welchen Wert n hat.
Tatsache ist aber, egal welches konstante k man wählt. Wenn n nur groß genug wird, ist log2(n) > k und die Ungleichung damit nicht erfüllt.
Fazit: O(n) wächst schneller als jede Potenzfunktion n^k.
Aber ob es damit eine Exponentialfunktion ist, weiß ich nicht. Dafür fehlen mir die mathematischen Grundlagen 
Hallo,
es ist formal nicht ganz sauber und die Definition der O-Notation ist nicht mit einbezogen, aber prinzipiell sieht das alles logisch aus. Man kann also ungefähr so zeigen, dass die genannte Funktion nicht polynomiell ist.
Etwas sauberer wäre das so:
Die zu untersuchende Funktion ist T(n) = n^(log2 n)
Wir behaupten, es gibt ein natürliches (oder auch positiv reelles) k, sodass T(n) element O(n^k) ist. (Bitte beachten, dass O(*) immer eine Menge von Funktionen beschreibt).
Das heißt, dass es ein natürliches n0 und ein positiv reelles c gibt, sodass
T(n) = n^(log2 n) n0
Die restlichen Umformungen sollten dann ähnlich zu deinen sein. Auch wenn das c etwas Ärger macht.
Nico
fair enough. Ich habe ja bereits geschrieben, dass ich das nie gelernt habe - Formfehler waren also zu erwarten.
Bevor ich aber in meinem Beweis mit c * n^k arbeiten würde, würde ich eher zeigen, dass c * n^k langsamer wächst als n * n^k = n^(k+1)
damit kann man sich das c schenken.
trotzdem danke für die Korrekturen