Landau, groß Theta < Funktionen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Seien f(n) und g(n) asymptotisch positive Funktionen. Beweisen sie unter Verwendung der Definition der [mm] \theta [/mm] Notation, dass max(f(n),g(n)) = [mm] \theta(f(n) [/mm] + g(n)) gilt |
Ich hab mir das jetzt ein bisschen angeschaut, und ich wäre da so rangegangen, dass ich ne Fallunterscheidung gemacht hätte.
Es gibt 3 Fälle:
1. f(n) [mm] \in [/mm] O(g(n))
2. g(n) [mm] \in [/mm] O(f(n))
3. f(n) [mm] \in \theta(g(n)) [/mm] bzw. g(n) [mm] \in \theta(f(n))
[/mm]
zu 1. Wenn f(n) [mm] \in [/mm] O(g(n)), dann ist ab einem bestimmten [mm] n_{0} [/mm] max(f(n),g(n)) = g(n) und f(n)+g(n) [mm] \in [/mm] O(g)
das wäre mein erster Ansatz.
Nur mal so grob dazu, was ich mir dabei gedacht habe. Bin ich da stark aufm Holzweg?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 01:42 Mi 05.12.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
