Gleichheit zweier Mengen < Mengenlehre < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:18 Sa 11.10.2008 | | Autor: | crash |
| Aufgabe | Zu zeigen:
c · O(g(n)) = O(g(n)), c > 0
f(n) [mm] \in [/mm] O(g(n)) [mm] \gdw \exists [/mm] c > 0 [mm] \exists n_{0} \ge [/mm] 1 [mm] \forall [/mm] n [mm] \ge n_{0} [/mm] : f(n) [mm] \le [/mm] c · g(n)
O(g(n)) ist übrigens die Ordnung der Wachstumsfunktion eines Algorithmus.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt. |
Ich hab versucht den Beweis zu führen, indem ich eine Funktion t(n) [mm] \in [/mm] O(f(n)) nehme und zeige, dass diese Funktion dann auch in der Menge c*O(f(n)) liegt. (Und umgekehrt).
Allerdings komm ich nicht weiter.
Es sei t(n) [mm] \in [/mm] O(f(n)) [mm] \Rightarrow [/mm] (mit den Bedingungen) t(n) [mm] \le [/mm] c*f(n)
Meine Idee war jetzt, abzuschätzen das t(n) [mm] \le [/mm] c*f(n) auch gilt, wenn ich die Konstante c quadriere, also
t(n) [mm] \le [/mm] (c*f(n)) *c
das ist aber nicht die Aussage das t(n) [mm] \in [/mm] c* O(g(n)) denk ich mal...
Hat jemand da einen Denkanstoss für mich?
Vielen Dank
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:22 So 12.10.2008 | | Autor: | uliweil |
Hallo crash,
Du solltest die beiden Konstanten c aus der Aufgabe und c aus der Definition auseinanderhalten und nicht gleich benennen. Und jetzt "geradeaus", also sei t(n) [mm] \in [/mm] O(g(n)), dann ex. nach Definition ein [mm] c_{1} [/mm] s.d. t(n) <= [mm] c_{1} [/mm] * g(n) ist. Betrachtet man nun [mm] c_{2}*t(n) [/mm] dann muss man eine Konstante [mm] c_{3} [/mm] finden, s.d. [mm] c_{2}*t(n) [/mm] < = [mm] c_{3} [/mm] * g(n). Na ja, was wird man da wohl nehmen ...
Gruß
Uli
|
|
|
|
