Big O Notation beweis?
Alsooo, ich hab von meinem Prof ein paar Übungsaufgaben zu BigO. Nur das Problem ist, dass Mathe in meinem Studiengang keine Priorität hat und ich deswegen aufgeschmissen bin. ChatGPT hat auch den Geist aufgegeben. Anyways..
Die Frage ist, ob xlog(x) E O(x^2) ist. Mein """Beweis""" sieht so aus gerade.
Ich bring mir das Zeug gerade alles selbst bei und höre L'Hôpital gerade das erste Mal, deswegen erstmal sorry!
Kurz. Ich habe gesehen dass ich INF durch INF teile und leite deswegen ab und sehe dass es wieder INF durch INF ist, also leite nochmal ab und sehe, dass der limes = 0 ist, x^2 also schneller wächst als xlogx und somit xlogx E O(x^2) ist.
Wo hab ich Fehler gemacht? Was ist richtig, was falsch?
Vielen Dank!
3 Antworten
0 ist richtig.
Ich hätte allerdings erstmal das x gekürzt und mit dem verbleibenden (log x)/x weitergerechnet. Die Definitionslücke bei 0 wäre mir da einfach egal gewesen, weil wir ja sowieso in Richtung Unendlich laufen wollen.
Deine Notation mit dem "L" gefällt mir nicht richtig. Du hast wie bei einem Compiler-Präprozessor in der Art eines Textersetzungs-Makros ein Kürzel definiert - auf den ersten Blick sieht das wie eine Multiplikation aus. Das kann man machen, während man auf der Suche nach der Lösung ist, aber für die tatsächliche Abgabeversion würde ich es ausschreiben.
Der große Bruch am Ende ergibt im Zähler 1/x und im Nenner nur die 2. (1/x)/2 = 1/(2x) (die 2x stehen unter dem Bruchstrich, hier nur zur besseren Erkennbarkeit geklammert). Der Ausdruck am Ende müsste also lauten: L 1/2x, was auch zu 0 wird.
Im Großen und Ganzen richtig.
Bis auf:
Im drittletzten Term
L ( (d log x) / (d x) ) / ( ( d (2 x) ) / (d x) )
hast du das "d" im Nenner des Zählers vergessen.
Im vorletzten Term hast du die 2 in den Zähler statt in den Nenner gesetzt.
Vermutlich wäre es auch besser,
(= inf / inf)
in Klammern zu setzen - damit deutlicher wird, dass es kein echter Term, sondern nur ein formaler Ausdruck ist (so kenne ich das aus mindestens einem Lehrbuch).
Übrigens wäre es etwas einfacher gewesen, gleich am Anfang ein x herauszukürzen.
Ja, Physik. Darüber hinaus das Eine und Andere über Vorlesungen für Mathematiker sowie autodidaktisch.
Die Aufgabenstellung ist nicht klar.
Falls es um den Grenzwert geht:
lim x -> +∞ ( x*log(x)/x² ) =
lim x -> +∞ ( log(x)/x ) = 0
denn es gilt log(x) < x für x -> +∞.
Falls es um die O-Notation geht:
T(n) ist O( f(n) ), falls T(n) ≤ c*f(n) für fast alle (großen) n
Hier gilt:
T(n) = n*log(n)
f(n) = n²
Es gilt n*log(n) < c * n², denn log(n) < n für grosse n.
Woher hast du dein mathematisches Wissen, wenn ich fragen darf? Studium?