Algorithmenlaufzeit + Beweis |
15.12.2009, 15:11 | joko2 | Auf diesen Beitrag antworten » |
Algorithmenlaufzeit + Beweis es geht in der Aufgabe darum die Laufzeit von 2 Algorithmen zu ermitteln und diese Aussage zu beweisen. Zwei Algorithmen sind gegeben: 1) Algorithmus 1 mit einer Laufzeit von O(f(n)) 2) Algorithmus 2 mit einer Laufzeit von O(g(n)) Algorithmus 3: BEGIN Führe Algorithmus 1 aus Führe Algorithmus 2 aus END Zusätzlich gelte f(n) ∈ ©(g(n)). Ermittle die Laufzeit und beweise deine Aussage. Nutze aus, dass f(n) ∈ ©(g(n)) gilt. Algorithmus 4: BEGIN IF n ≥ 30 Führe Algorithmus 1 aus ELSE Führe Algorithmus 2 aus END IF END Welche Laufzeit hat der Algorithmus? Beweise deine Aussage. Zu 3: Da f(n) höchstens so schnell wächst wie g(n), aber durch "f(n) ∈ ©(g(n))" auch gegeben ist, dass f(n) mindestens so schnell wie g(n) wächst, heißt das, dass die Laufzeit 2* O(f(n)) ist oder wie darf ich das verstehen? Zu 4: Ist das dann so einfach, dass man sagen kann, dass falls n ≥ 30 ist, ist die Laufzeit dann O(f(n)) ist und falls n < 30 dann O(g(n)) oder ist das noch komplexer? Hoffe da kann mir jemand weiterhelfen |
||
15.12.2009, 15:29 | kiste | Auf diesen Beitrag antworten » |
In der Art und Weise nicht lesbar. Schau doch wenigstens ob das Copy und Paste funktioniert wenn du das schon machst, |
||
15.12.2009, 16:00 | joko2 | Auf diesen Beitrag antworten » |
RE: Algorithmenlaufzeit + Beweis Ich hab das ganz nicht mit Copy und Paste eingefügt, sondern nur ein paar Sonderzeichen von google, aber die scheinen hier nicht zu funktionieren. Hab jetzt nach Latexsonderzeichen gesucht und es funktioniert Zwei Algorithmen sind gegeben: 1) Algorithmus 1 mit einer Laufzeit von O(f(n)) 2) Algorithmus 2 mit einer Laufzeit von O(g(n)) Algorithmus 3: BEGIN Führe Algorithmus 1 aus Führe Algorithmus 2 aus END Zusätzlich gelte f(n) (g(n)). Ermittle die Laufzeit und beweise deine Aussage. Nutze aus, dass f(n) (g(n)) gilt. Algorithmus 4: BEGIN IF n 30 Führe Algorithmus 1 aus ELSE Führe Algorithmus 2 aus END IF END Welche Laufzeit hat der Algorithmus? Beweise deine Aussage. Zu 3: Da f(n) höchstens so schnell wächst wie g(n), aber durch "f(n) (g(n))" auch gegeben ist, dass f(n) mindestens so schnell wie g(n) wächst, heißt das, dass die Laufzeit 2* O(f(n)) ist oder wie darf ich das verstehen? Zu 4: Ist das dann so einfach, dass man sagen kann, dass falls n 30 ist, ist die Laufzeit dann O(f(n)) ist und falls n < 30 dann O(g(n)) oder ist das noch komplexer? |
||
15.12.2009, 19:20 | kiste | Auf diesen Beitrag antworten » |
3.) Warum sollte f höchstens so schnell wachsen wie g? Das 2* kannst du weglassen, das kann man durch den O-Term "kodieren". Genauer gilt übrigens dass der Algorithmus in liegt. 4.) Beachte dass die Landausymbole hier Aussagen für n gegen unendlich treffen! |
||
15.12.2009, 20:05 | joko2 | Auf diesen Beitrag antworten » |
3) Das f höchstens so schnell wächst wie g hab ich wohl falsch gelesen. Wie kodiere ich das denn dann in den O-Term? O(2n) als Laufzeit? Wie mir helfen soll, versteh ich auch nicht. 4) Heißt das dann, dass bei die Laufzeit ist? |
||
15.12.2009, 21:52 | joko2 | Auf diesen Beitrag antworten » |
Wenn ich das nun richtige sehe, dann sollte Algorithmus 4, die Laufzeit O(f(n)) haben, da bei n gegen unendlich, nur Algorithmus 1 ausgehführt wird, also n0=30 ist, ist das korrekt? Aber bei Algorithmus 3, komm ich noch net ganz weiter, ist das dann einfach O(f(n)) + O(g(n)) ? |
||
Anzeige | ||
|
||
15.12.2009, 21:54 | kiste | Auf diesen Beitrag antworten » |
Beides korrekt. Wie du im vorigen Beitrag auf n^n kommst ist mir wieder ein Rätsel. Bei 3.) war die Lösung... |
||
15.12.2009, 22:03 | joko2 | Auf diesen Beitrag antworten » |
Ich weiß auch nicht mehr genau wie ich auf n^n kam, manchma denke ich ein wenig konfus. Aber wie du für 3) auf die Lösung kommst, ist mir nicht wirklich klar, könntest du das noch ein wenig näher erläutern? Aber schonma vielen Dank für die Hilfe |
||
15.12.2009, 22:21 | kiste | Auf diesen Beitrag antworten » |
theta war geistige verwirrung, O(f) passt |
||
15.12.2009, 22:24 | joko2 | Auf diesen Beitrag antworten » |
Naja, für 3) dachte ich, dass man beide Laufzeiten addiert, also O(f(n)) + O(g(n)) erhält, wieso das nur O(f) sein soll, ist mir auch nicht wirklich klar, da ja beide hintereinander ablaufen. |
||
15.12.2009, 22:26 | kiste | Auf diesen Beitrag antworten » |
Da ist |
||
15.12.2009, 22:31 | joko2 | Auf diesen Beitrag antworten » |
Ajo stimmt, mir war die Zusatzbedingung f(n) (g(n)) schon wieder ganz entfallen. Oki vielen Dank, hier ist dann alles klar |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|