Landau-Notation |
24.03.2009, 20:42 | Auf diesen Beitrag antworten » |
hilfe | 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 |
|
|
24.03.2009, 20:45 | Auf diesen Beitrag antworten » |
chuckice | so, diesmal registriert Hallo, bin endlich registriert. Gibts hier kein Latex? |
06.04.2009, 20:01 | Auf diesen Beitrag antworten » |
Ich | 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. |
23.04.2009, 22:11 | Auf diesen Beitrag antworten » |
JanS | 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?.. |
Anzeige | |
|
|