Landau < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:34 Do 09.02.2006 | | Autor: | AriR |
| Aufgabe | Betrachten Sie die Funktion f(n) = [mm] 34*n^2*log(n) [/mm] + 18 [mm] *n^2 [/mm] +3*(n +1) und
eine obere Schranke O(n2 * log(n)). Zeigen Sie nun formal, dass es sich bei dieser Schranke tatsächlich um
eine obere Schranke handelt. Beweisen Sie weiter, dass es sich zudem um eine untere Schranke handelt. |
(FRAGE zuvor nicht gestellt)
Hey Leute, bekomme das einfach mal wieder nicht hin :(
habe bei dem teil mit der oberen schrank am ende sowas stehe wie:
18n+6 [mm] \le [/mm] K *log(n) wobei k eine beliebe konstante sein soll
hat jemand von euch eine idee, wie man hier weitermachen kann, oder wie die Aufgabe überhaupt lösen kann?
danke schonmal im voraus... gruß Ari
|
|
| |
|
Hallo und guten Morgen aus Bonn !
Du willst also [mm] f(n)=O(n^2\log [/mm] (n)) zeigen und [mm] f(n)=\Omega(n^2\log [/mm] (n)), nicht wahr ?
Dabei ist
f(n)=O(g(n)) genau dann, wenn es eine Konstante C und ein [mm] n_0 [/mm] gibt, so dass fuer alle
[mm] n\geq n_0 [/mm] gilt: [mm] f(n)\leq C\cdot [/mm] g(n).
Also:
[mm] f(n)=34\cdot n^2\cdot\log (n)\: +\: 18\cdot n^2\: +\: 3n\: +\: [/mm] 3
[mm] \leq 34n^2\log(n) +18n^2\log (n)+3n^2\log [/mm] n [mm] +3n^2\log (n)=58\cdot n^2\log [/mm] n
fuer alle [mm] n\in\IN, [/mm] fuer die [mm] 1\leq \log [/mm] (n) gilt, d.h. fuer alle [mm] n\geq n_0=2 [/mm] (fuer Zweier-Log, sonst halt [mm] n_0=Basis, [/mm] zu der Du [mm] \log [/mm] nimmst), nicht wahr (die einzelnen Summanden sind
''brutal'' nach oben abgeschaetzt).
Dies zeigt schon mal den ersten Teil.
Es gilt weiter [mm] f(n)=\Theta [/mm] (g(n)) genau dann, wenn es eine Konstante c>0 und ein [mm] n_0 [/mm] gibt, so daß fuer alle [mm] n\geq n_0
[/mm]
[mm] f(n)\geq c\cdot [/mm] g(n)
gilt. Sicherlich gilt doch aber hier fuer n so, [mm] da\3 \log (n)\geq [/mm] 1,
dass
[mm] f(n)\geq 34\cdot n^2\log (n)\geq n^2\cdot\log [/mm] (n), also nimm (fuer Zweier-Logarithmus)
n=2 und c=1.
Viele Gruesse,
Mathias
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:01 Do 09.02.2006 | | Autor: | AriR |
lol das war ja einfach.. vielen dank :)
|
|
|
|
