Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Frage zur Übungen
Hallo Zusammen,
hier unten ist die Antwort der Aufgabe 9b die die Laufzeit erklärt:
• In den ersten (n − 1)/4 = |w|/2 Durchläufen wird jeweils zweimal mindestens über n/2 Zeichen iteriert. Entsprechend ist die Laufzeit auch Ω(n hoch2) und damit insgesamt Θ(n hoch2).
(n − 1)/4 = |w|/2 >>> Welche Teil ist es im Wort (w#w hochR) ?
Was ist der Intuition unter “Entsprechend ist die Laufzeit auch Ω(n hoch2) und damit insgesamt Θ(n hoch2)”?
Ich freue mich auf jeder Feedback.
Viele Grüße
Pelin
Sag doch erstmal um welche Aufgabe auf welchem Blatt es sich handelt.
Groß Omega ist ja eine untere Schranke, wenn man also sagen kann, dass die Laufzeit von Algorithmus mindestens xzy ist, dann ist die Laufzeit in Ω(xyz).
Warum die Laufzeit insgesamt in Θ ist kann man aus deinem Text nicht rauslesen, wahrscheinlich weil die obere Schranke (groß O) schon ausgerechnet wurde.
Und wenn die obere und untere Schranke gleich ist, dann kann man anstatt Ω und O auch Θ schreiben.
PS: als “hoch” Zeichen nimmt man idR dieses hier: ^
Hallo Jonas,
Danke für deine Antwort.
Meine Frage ist aus dem Blatt 2 / Aufgabe 9b.
Sei L = {w#w^R | w ∈ {0,1}∗}. Dabei bezeichnet w^R das Spiegelwort zu w, also z. B. (001)^R = 100
Die Frage ist: wieviel Zeit benötigt die Maschine (in Θ-Notation!) in Abhängigkeit von der Eingabelänge n.
Die gesamte Antwort zur Laufzeit ist:
• In jedem Durchlauf (1× ganz nach rechts laufen + 1× ganz nach links laufen) werden je 2 Zeichen entfernt und dabei Θ(|w#w^R|) = Θ(n) viele Schritte ausgeführt. Es kann also maximal O(n) viele Durchläufe geben.
• Es kann aber (sofern die Eingabe zumindest größtenteils passt) auch Ω(n) viele Durchläufe geben.
• Sollte irgendwann etwas unerwartetes auftreten hält die TM sofort verwerfend.
• Ansonsten hält sie akzeptierend nachdem alle Zeichen bis auf das mittlere # entfernt wurden. Entsprechend ist die Laufzeit in O(n^2).
• In den ersten (n − 1)/4 = |w|/2 Durchläufen wird jeweils zweimal mindestens über n/2 Zeichen iteriert. Entsprechend ist die Laufzeit auch
Ω(n^2) und damit insgesamt Θ(n^2).
Ja, du hast Recht, die obere Schrank wurde schon gerechnet als O(n^2).
Meine Erklärung für den Grund von O(n^2): n Durchläufe, und in jeder Durchlauf n Schritte als obere Schrank.
Stimmt es?
Ich kenne die Aufgabe nicht, würde aber gerne folgende Verbesserungsvorschläge zur Diskussion stellen.
Da …, gibt es O(n)-viele Durchläufe.
Da …, gibt es Ω(n)-viele Durchläufe.
Ich verstehe, was du meinst, wenn du [m] <Ω oder O>(n)-viele Durchläufe[/m] schreibst, denke aber, dass das formal schwierig ist. Im Zweifel haben die Adjektive nur eine narrative, aber keine formale Semantik. (Sprich: es macht den Text einfacher zu lesen, ändert aber keine formale Bedeutung.)