Theta Abschätzung gesucht < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Also die Fragestellung lautet eine "Theta" Abschätzung für folgenden Ausruck zu finden:
(n³-2n²-4)/(n³+2n²+3n)
Eine theta abschätzung ist halt der Schnitt einer O und Omega abschätzung, also eine Funktion f die genau gleichschnell steigt wie eine Funktion g liegt in Theta(g). |
So,
der obige Part ist nicht wirklich die "genaue" Angabe der Aufgabe.
Die genauen Definitionen der Landauschen Symbole gibts hier:
http://de.wikipedia.org/wiki/Landau-Symbole
Theta ist also wie oben geschrieben der Schnitt aus O(f(n)) und Omega(f(n)) ... Also man muss eine Abschätzung finden, die Teil beider Mengen ist.
Also generel muss ich sagen, dass ich bei dieser Art der Aufgaben Probleme habe. Die Abschätzung muss man ja mehr oder minder Intuitiv eraten und dann nachweisen. Oder gibts da Möglichkeiten nicht ganz so "Intuitiv" vorzugehen. Intuitiv hätte ich jetzt gesagt, die Abschätzung ist Theta(1) .. also O(1) und gleichzeitig Omega(1) ...
Ich hab das auch mal versucht nachzurechnen und für O(1) hat das super geklappt, allerdings komme ich bei Omega(1) nicht weiter.
Wahrscheinlich ist die Abschätzung komplett falsch... Vielleicht kann mir hierbei auch jemand den Hinweis geben, was eine richtige Abschätzung wäre. Nachweisen muss ich die Abschätzung ja trotzdem noch.
Also hier mal mein Rechenweg, vielleicht stimmts ja doch so in etwa, und man kommt auch bei Omega irgendwie noch auf die Omega(1) Abschätzung:
http://img397.imageshack.us/img397/3883/mathenq1.gif
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:35 Sa 17.05.2008 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
