Algorithmenlaufzeit + Beweis

Neue Frage »

joko2 Auf diesen Beitrag antworten »
Algorithmenlaufzeit + Beweis
Heyo,

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 weiterhelfensmile
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,
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 funktioniertsmile

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?
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!
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?
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)) ?
 
 
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...
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 Hilfesmile
kiste Auf diesen Beitrag antworten »

theta war geistige verwirrung, O(f) passt
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.
kiste Auf diesen Beitrag antworten »

Da ist
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 klarsmile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »