---

Geschrieben von hilfe am 24.03.2009 um 20:42:

  Landau-Notation

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

---

Geschrieben von chuckice am 24.03.2009 um 20:45:

  so, diesmal registriert

Hallo, bin endlich registriert. Gibts hier kein Latex?

---

Geschrieben von Ich am 06.04.2009 um 20:01:

  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.

---

Geschrieben von JanS am 23.04.2009 um 22:11:

 




kann mir das wer erklären??

teta heisst doch g(x)==f(x)
omega heisst g>=f(x)
und O g(x) <= f(x)

wie kann etwas was gleich is gleichzeitig größer und kleiner sein??

mfg
Jan

== =>= U <= hat sich erledigt xD

wenn nach der omega-klasse von g(x) gefragt wird.. extrahiert man dann auch das schnellstwachsenste glied oder das langsamst??

also nimmt man ei g(x) = 2x+3^x omega(3^x) oder 2x?..