 Landau-Notation |
hilfe
unregistriert
 |
|
Hallo,
mit Hilfe der Landau- Notation kann ich ja herausfinden, welche Funktion die Laufzeit eines Algorithmus f(n) bei potenziell unendlichen n-Eingaben "deckelt" oder beschränkt.
Wenn ich mathematisch Beweisen soll, dass folgendes Beispiel für
[latex]
f(n) = O(g(n))
[/latex]
gilt.
[latex]
f(n) = \sqrt(n)
g(n) = 1000*n
[/latex]
Ich würde folgende Ungleichung aufstellen:
[latex]
f(n) <= k * g(n) , n >= 1
\sqrt(n) <= k * 1000*n
[/latex]
Aber wie gehts dann weiter? Habe heute schon so viele falsche Rechnungen gesehen und brauch einmal eine richtige.
Grüße
|
|
24.03.2009 20:42 |
|
|
chuckice
Grünschnabel
Dabei seit: 24.03.2009
Beiträge: 1
|
|
Hallo, bin endlich registriert. Gibts hier kein Latex?
|
|
|
24.03.2009 20:45 |
|
|
Ich
unregistriert
|
|
| RE: so, diesmal registriert |
     |
Ich würde einfach sagen:
sqrt(x)=x^(0.5) <= x^(1) (für x=>1).
Somit wäre es schon bewiesen.
|
|
|
06.04.2009 20:01 |
|
|
|
