Landau-Notation < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:02 Mi 06.11.2013 | | Autor: | Mopsi |
| Aufgabe | Zeigen Sie:
1. [mm] O(f(n)) + O(g(n)) = O(f(n) + g(n))[/mm]
2. [mm] 2^{n+d} \in O(2^n), d \in \IN, konstant[/mm]
3. [mm] O(f(n))^{O(g(n))} \neq O(f(n)^{g(n)})[/mm]
4. [mm] O(log_a n) = O(log_b n), \textrm{für a, b > 1}[/mm] |
Guten Abend :)
Wir sollen das als Hilfe verwenden:
http://www7.pic-upload.de/06.11.13/lqo9beizjfrb.jpg
Wie soll mir das aber jetzt bei 1. helfen?
Ich habe leider gar keine Idee :(
Könnt ihr mir bitte nur einen kleinen Tipp geben?
Viele Grüße,
Mopsi
|
|
| |
|
Hallo,
> Zeigen Sie:
>
> 1. [mm] O(f(n)) + O(g(n)) = O(f(n) + g(n))[/mm]
> 2. [mm] 2^{n+d} \in O(2^n), d \in \IN, konstant[/mm]
>
> 3. [mm] O(f(n))^{O(g(n))} \neq O(f(n)^{g(n)})[/mm]
> 4. [mm] O(log_a n) = O(log_b n), \textrm{für a, b > 1}[/mm]
>
>
> Guten Abend :)
>
> Wir sollen das als Hilfe verwenden:
> http://www7.pic-upload.de/06.11.13/lqo9beizjfrb.jpg
>
> Wie soll mir das aber jetzt bei 1. helfen?
>
> Ich habe leider gar keine Idee :(
Na, wieso nicht? Mit dem gegebenen Infozettel hast du doch nur die Definition ganz oben, die du verwenden kannst.
Die musst du hernehmen.
In 1. ist eine Mengengleichheit zu zeigen; das macht man, indem man beide Teilmengenbeziehungen [mm]\subseteq[/mm] und [mm]\supseteq[/mm] zeigt.
Ich mache mal die Richtung [mm]\supseteq[/mm]
Zu zeigen ist als [mm]\mathcal O(f(n)) \ + \ \mathcal O(g(n)) \ \supseteq \ \mathcal O(f(n)+g(n))[/mm]
Dazu müssen wir ein bel. Element der Menge rechterhand hernehmen und zeigen, dass es gefälligst auch in der Menge linkerhand liegt.
Nehmen wir also ein beliebiges [mm]t(n)\in\mathcal O(f(n)+g(n))[/mm] her.
Das bedeutet nach der obersten Definition auf deinem Zettel:
Es gibt ein [mm]c>0[/mm] und ein [mm]n_0\ge 1[/mm], so dass für alle [mm]n\ge n_0[/mm] gilt:
[mm]t(n) \ \le \ c\cdot{}(f(n)+g(n)) \ = \ \red{c\cdot{}f(n)} \ + \ \blue{c\cdot{}g(n)}[/mm]
Und was bedeutet das?
>
> Könnt ihr mir bitte nur einen kleinen Tipp geben?
>
> Viele Grüße,
> Mopsi
>
>
Gruß
schachuzipus
|
|
|
|
