Seite 1 von 1

Programmieraufgabe: Frage zur geforderten Laufzeitkomplexität

Verfasst: 11. Apr 2016 16:28
von Stefan1992
Hallo,

ich habe mal wieder eine Frage zur geforderten Laufzeitkomplexität der Algorithmen. Und zwar ist gefordert, dass die Algorithmen die im Wiki angegebene Komplexität unter allen Umständen einhalten.

Ich versuche jedoch die Empfehlung aus der Vorlesung einzuhalten, die Algorithmen als Iterator zu implementieren.
In Java bedeutet das, dass die Algorithmen eine next()- und eine hasNext()-Methode implementieren müssen.
Dabei beinhaltet, zumindest nach meinem Verständnis, die next()-Methode den eigentlichen Induktionsschritt des Algorithmus und die hasNext()-Methode prüft, ob die Abbruchbedingung erfüllt ist.
Das heißt für mich: Die hasNext()-Methode kann den Zustand der Datenstruktur verändern, wohingegen die next()-Methode dies nicht tut.

Betrachtet man nun beispielsweise den Ford-Fulkerson, so wird in einem Induktionsschritt ein flusserhöhender Pfad gesucht. Die Abbruchbedingung ist, dass kein flusserhöhender Pfad mehr im Netzwerk existiert.
Um die Abbruchbedingung zu überprüfen, muss ich also auf jeden Fall noch einmal eine Tiefensuche über das Netzwerk laufen lassen. Um den Zustand der Datenstruktur allerdings nicht zu verändern, müsste ich das "lokal" prüfen, ohne den Zustand zu verändern.
Erst wenn die Überprüfung des Algorithmus ergibt, dass ein flusserhöhender Pfad existiert, sollte der Induktionsschritt (in dem erneut der Pfad gesucht wird) ausgeführt werden.

Also würde der so implementierte Algorithmus im Prinzip die Tiefensuche doppelt ausführen und somit genau genommen nicht der angegebenen Laufzeitkomplexität entsprechen.
Eine Möglichkeit wäre natürlich, einen eventuell gefundenen Pfad bei der Überprüfung der Abbruchbedingung zu speichern und bei Aufruf der next()-Methode zu verwenden.
Allerdings würde das meiner Meinung nach nicht der geforderten (Java-)Iterator-API entsprechen, da ich so unter Umständen den Zustand der Datenstruktur durch die hasNext()-Methode verändern kann.

Deshalb meine Frage: Wie genau soll die Laufzeitkomplexität eingehalten werden?


Grüße Stefan

Re: Programmieraufgabe: Frage zur geforderten Laufzeitkomplexität

Verfasst: 11. Apr 2016 20:58
von Prof. Karsten Weihe
Stefan1992 hat geschrieben: Also würde der so implementierte Algorithmus im Prinzip die Tiefensuche doppelt ausführen und somit genau genommen nicht der angegebenen Laufzeitkomplexität entsprechen.
Eine Verdopplung der Laufzeit ergibt dieselbe Komplexität :!: :idea:

Schauen Sie noch einmal in dieses Kapitel in der GdI II hinein.

Mit "Iterator" ist im Wiki auch nicht unbedingt java.util.Iterator gemeint, sondern allgemein das Design Pattern Iterator: https://de.wikipedia.org/wiki/Iterator_(Entwurfsmuster). Vor allem die englischsprachige Seite https://en.wikipedia.org/wiki/Iterator_pattern zeigt mit der Auflistung der Realisierungen in verschiedenen Sprachen, welche Bandbreite an Designs dieses Pattern erlaubt.

Aber: Es ist keine Anforderung der Aufgabenstellung, Algorithmen als Iteratoren zu implementieren.

KW

Re: Programmieraufgabe: Frage zur geforderten Laufzeitkomplexität

Verfasst: 12. Apr 2016 11:56
von Stefan1992
Vielen Dank für die Hinweise! :)