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.
Lösungsvorschlag Mini-Klausur WS17/18 erstellt: Frage zu Space Complexity in AuD
Hey Leute, ich habe mal einen Lösungsvorschlag zur Mini-Klausur WS 17/18 erstellt, bzw. zu den ersten beiden Aufgaben, die ADT Aufgabe wurde schon in diversen AKs abgefragt und müsste demnach noch in irgendwelchen anderen Lösungsvorschlägen herumgeistern…
Die Korrektheit der Lösungen kann ich selbstverständlich nicht garantieren, da ich die Backtracking jetzt nicht ausgiebig getestet habe.
Link: https://fsi.cs.fau.de/dw/pruefungen/bachelor/aud/loesung-miniklausur-17
Hätte aber z.B. bei der c) eine allgemeinere Frage zu der Definition von Space Complexity in AuD:
Ich hab leider keine Ahnung wie genau denn Speicherbedarf definiert ist bei uns (steht das in den Vorlesungsslides irgendwo?)
Ich habe jetzt bei der c) mal O(1) angekreuzt, da wir ja nur 2 Variablen instanziieren, wobei die eine auf eine bereits vorhandene (n) zeigt und nur die andere y = 0 angelegt wird. Hier passiert nichts rekursives und es werden keine Arrays oder so erstellt, deswegen kam mir da ein konstanter Speicherbedarf logisch vor.
Aber wie läuft das generell, v.a. im Hinblick auf rekursive Methoden? Ein gutes Beispiel ist da die WS 17/18 1b) zum Speicherbedarf verschiedener rekursiver / DP / iterativer Varianten von Fibonacci. Kann das jemand ausführlich erklären was zum Beispiel bei jener Aufgabe korrekt /falsch ist, bzw. einen kleinen Guide für Space Complexity (v.a. im Hinblick auf Rekursion) geben?
Vielen Dank!
Angenommen n ist kleiner als m und m ist größer als y, dann würde der Wert x den Wert 0 erreichen und die Funktion würde nicht terminieren => x kann keine Terminierungsfunktion sein. T:=(m-y)+n dagegen sollte eine gültige Terminierungsfunktion darstellen.
- fällt streng monoton mit jedem Schleifendurchlauf
- nimmt nur ganzzahlige Werte an
- ist nach unten durch 0 beschränkt, siehe n > 0 und y < m