Asymptotische Abschätzungen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo!
Ich weiß bei solchen Aufgaben nicht, wie ich da vorzugehen habe, um die Behauptungen zu zeigen bzw. zu widerlegen. Ich bitte deshalb zu Hilfe. Vielleicht kann mir jemand hilfreiche Tipps geben.
Ich soll folg. Behauptungen beweisen oder widerlegen:
1. f(n) + g (n) = Teta (max(f(n),g(n)))
2.Wenn f(n) = O(g(n)) ist, so auch [mm] 2^{f(n)} [/mm] = [mm] O(2^{g(n)})
[/mm]
Hier ist mit O die Groß-O-Notation gemeint, also dass die Funktion f(n) durch eine größere Funktion g(n) dominiert wird, f(n) [mm] \le [/mm] c g(n) für eine Konstante c.
Die Teta-Notation bedeutet, dass ein Funktion von links und von rechts von g(n) eingeschränkt wird, also a g(n) [mm] \le [/mm] f(n) [mm] \le [/mm] b g(n) für a,b Konstanten.
Vielen Dank!
Gruß, Milka
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:41 So 30.04.2006 | | Autor: | xamurai |
f(n) + g (n) = Teta (max(f(n),g(n)))
==>
f(n) + g (n) = O(max(f(n),g(n)))
und
(max(f(n),g(n))) = O(f(n) + g (n))
-----
du brauchst da c1 und c2
sei z.B. f = max (f,g)
dann muss es c1 , c2 geben so dass
f +g <= c1.(f)
und
f <= c2.(f+g)
f <= c2.(f) + c2.(g)
zB : für |f| >= |g| und c2 >=2
ist f <= c2.(f) +c2.(g)
für c1 >= 2 ist
f + g <= c1.(g)
da f = max(f,g)
=> es exist. c1,c2 >0 , [mm] n_0 [/mm] aus IN so dass für alle n >= [mm] n_0
[/mm]
f+g = Theta(max(f,g))
!!! aber diese ganze geschichte müss von einem mathen Student(in) überprüfen werden :))
|
|
|
|
