O-Kalkül < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 16:42 Di 25.06.2013 | | Autor: | bandchef |
| Aufgabe | Welche der Schranken gelten für diese Beziehung?
$f(n) = [mm] \Omega(g(n))$ [/mm] mit $f(n) = [mm] n^2$ [/mm] und $g(n) = [mm] 3n\cdot log_2(n)$ [/mm] |
Durch "ansehen" erkennt man, dass [mm] $3n\cdot log_2(n)$ [/mm] nur eine untere Schranke sein kann. Somit trifft die obere Schranke und die exakte Schranke nicht zu.
Genaue Berechnung der unteren Schranke:
Definition: [mm] $\Omega(g(n)) [/mm] = [mm] \{f(n) | \exist c \in \mathbb R^{+}, n_0 \in \mathbb N: \forall n \geq n_0, f(n) \geq c\cdot g(n)\}
[/mm]
[mm] $n^2 \geq [/mm] 3n [mm] \cdot log_2(n) \cdot [/mm] c [mm] \Leftrightarrow \frac{n}{3\cdot log_2(n)} \geq [/mm] c$ mit $n=2$ wird der Term auf der linken Seite des Ungleichheitszeichen so klein wie möglich (es ist ja die untere Schranke gefordert!). Wenn ich n=2 einsetze, kommt [mm] \frac23 [/mm] raus und jetzt sollte ich noch ein c [mm] \leq \frac23 [/mm] finden, was laut Definition der unteren Schranke nicht geht, weil $c [mm] \in \mathbb R^{+}$ [/mm] gefordert ist und so keine 0 enthalten ist!
$3n [mm] \cdot log_2(n)$ [/mm] IST aber eine untere Schranke; schon alleine wegen meiner Lösung. Ich hab hier aber keinen Rechenweg, sondern nur eine Angabe, dass es eben eine untere Schranke ist!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:23 Di 25.06.2013 | | Autor: | bandchef |
Ich hab meinen Denkfehler selber gefunden! Es gilt $c [mm] \in \mathbb [/mm] R{+}$ es dreht sich ja hier um reelle Zahlen ohne die 0! Ich kann also locker eine Zahl c aus $R{+}$ finden bspw.: [mm] \frac13!
[/mm]
Und so gilt auch die untere Schranke!
|
|
|
| |
|
So, jetzt hab ich aber dennoch noch eine Frage:
wenn ich die obere Schranke für die gleiche Aufgabe berechnen soll, sieht das nun so aus:
[mm] $\frac{n}{3 \cdot log_2(n)} \leq [/mm] c [mm] \overbrace{\Leftrightarrow}^{\text{l'H}} \frac13\cdot \lim_{n\to \infty}\left( n\cdot ln(2) \right) \leq [/mm] c [mm] \Leftrightarrow "\infty" \leq [/mm] c$
Ich soll also hier nun ein c finden, dass "größergleich" unendlich ist. Das soll ich doch finden, oder? Ich meine die reellen Zahlen sind ja unendlich oder? Somit würde, ja die obere Schranke auch wieder passen, was aber laut Lösung nicht darf!
Wo ist hier mein Denkfehler?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Do 27.06.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
