Bestimmen Sie eine möglichst einfache Funktion...

Neue Frage »

loci Auf diesen Beitrag antworten »
Bestimmen Sie eine möglichst einfache Funktion...
g(n) mit

3n log (n!) + (n²+3) log n = Theta (g(n))

Als Tipps haben wir bekommen, die Rechenregeln auszunutzen (welche weiß ich nicht).

Ich habe mir versucht Gedanken über die Aufgabe zu machen. Eine Möglichkeit wäre, n abzuschätzen. Aber Frage ist halt, wie. Und was ich daraus folgern kann. Zu den "Rechenregeln" - mir fallen da jetzt keine Logarithmengesetze oder sowas ein, wie man das so umstricken kann, dass es einfacher wird.

Von den Landausymbolen her wächst bei Theta ja g genauso schnell wie F. Bzw. hier die linke Seite genau so schnell wie g(n).

Hat jemand einen Tipp wie ich anfangen könnte?
HAL 9000 Auf diesen Beitrag antworten »

Eigentlich kann man hier doch sehr grob rangehen: Es ist und somit .
loci Auf diesen Beitrag antworten »

Hallo und Danke für das Feedback!

Also d.h. dass ich einfach abschätzen muss (wegen "grob rangehen") statt groß rumrechnen?

Oder kann ich daraus zum Beispiel das "+3" aus der Klammer von (n²+3) weglassen? Das ist doch vernachlässigbar gering, oder? Kann ich einfach aus 3n log (n!) schließen, dass ich dort auch einfach log (n!) einsetzen könnte und für (n²+3)*log n auch einfach n²+log (n) setzen könnte, sodass ich

log (n!) + n² * log n = Theta (g(n)) habe oder reicht abschätzen nicht? Bin mir noch nicht ganz klar auf was die Aufgabe speziell heraus will.
HAL 9000 Auf diesen Beitrag antworten »

Ich wollte sinngemäß sagen, dass es im vorliegenden Fall reicht, grob abzuschätzen - nicht, dass man das stets auch muss. Mitunter muss es doch wesentlich genauer zugehen, aber hier eben nicht.

Mit der von mir oben genannten Abschätzung folgt dann nämlich für den Gesamtterm nach unten



und nach oben für alle

.

Und schon kann man wählen, was dem Aufgabenersteller wohl einfach genug sein sollte. smile
loci Auf diesen Beitrag antworten »

Ah ok. Ich habe das zwar auch raus, aber habe ich nur in eine Richtung abgeschätzt, nämlich geschaut, was von beiden Teilen am größten ist. Muss man immer in jedem Fall auch eine Abschätzung nach unten machen? Ich habe einfach folgendes überlegt gehabt:

3n log (n!) + (n²+3) log n wachsen genauso schnell wie g(n).

1. Schritt: Weglassen von unnötigen Termen:

n log (n!) + (n²) log n wachsen genauso schnell wie g(n).

2. Überlegen was von beiden Teilen am schnellsten wächst (hier wa ich mir zuerst nicht sicher, ob das n log (n!) oder (n²) log n ist - das muss man dann aber nachschlagen, hatte jetzt in meiner Überlegung (erstmal im Kopf probiert) vermutet dass n²*log n am schnellsten wächst. Daher wäre das meine Lösung gewesen da man n log (n!) vernachlässigen kann.

Sieht ja aus als sei die Überlegung nicht ganz dumm gewesen. Aber muss ich dann nicht schreiben

(g(n)) = n²*log n, statt nur g(n) = n²*log n ? Ich will ja sagen dass g(n) genauso schnell wächst wie n²*log n, oder warum kann ich das Theta weglassen?
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von loci
Muss man immer in jedem Fall auch eine Abschätzung nach unten machen?

Für nicht, aber für schon - schau dir doch nochmal genau die Definition dieser beiden Landau-Symbole an!
 
 
loci Auf diesen Beitrag antworten »

Stimmt! Bei Theta steht (Beispiel: f(n) = (g(n)) ) ist asymptotisch sowohl von unten als auch von oben durch g(n) beschränkt. f(n) und g(n) wachsen gleich schnell.

Bei näherer Betrachtung macht das ja auch Sinn, denn wenn es "genauso schnell wie" wächst, muss es ja 2 Schranken geben, in denen sich das alles bewegt (stelle es mir gerade bildlich als Graph im Koordinatensystem vor). Wenn es "nur" schneller oder "nur" langsamer wächst, würde ich daraus ableiten, dass nur eine Abschätzung nach oben bzw. unten notwendig ist.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »