asymptotische notation < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:33 So 24.04.2011 | | Autor: | core_1 |
| Aufgabe | Es seien f,f1,f2,g,g1,g2 : [mm] \IN\to\IR_{\ge0} [/mm] Funktionen.
zeigen oder wiederlegen Sie:
1. f=O(g) [mm] \Rightarrow 2^{f} [/mm] = [mm] O(2^{g})
[/mm]
2. f=o(g) [mm] \Rightarrow [/mm] f=O(g)
3. f=O(g) [mm] \Rightarrow [/mm] f=o(g) |
Bei der 1. fehlt mir ihrgendwie der Ansatz - ich könnte mir eine Beispiel rechnung ausdenken, da würde ich es aber nur für einen Fall zeigen. Das reicht nicht?
Wäre cool, wenn mir einer einen Denkanstoss geben könnte.
Bei der 2. ist es ja eigt. klar, f=o(g) bedeutet ja f wächst langsamer als g und f=O(g) heißt f wächst höchstens so schnell wie g!
daraus folgt, dass aus f=o(g) --> f=O(g) folgen kann aber nicht aus f=O(g) --> folgt.
Aber wie zeig ich das? :D oder reicht das, wenn ich das so aufschreibe.
gruß und danke schonmal =)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:24 Di 26.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
