Laufzeit von einem Algorithmus bestimmen

[Kirby.exe]

Also ich lerne gerade für meine Datenstrukturen & Algorithmen Klausur und arbeite deshalb gerade die Probeklausur durch. Hier ist die Aufgabe:

Gibt es eine großes Schema wie man z.B. die initialisierung gewichtet oder passiert dies immer in O(1) ? Woran mache ich hier fest wie lange die Queue durchlaufen wird?

 

[LimDul]

Grundsätzlich hast du eine Menge von Elementen die du bearbeitest. Jede Operation auf einem dieser Elemente ist - solange nichts anderes gesagt wird O(1).

Das heißt Schritt 3 ist - da nichts anderes angegeben ist - O(1). Schritt 1 z.B. wäre Laufzeit n, da du alle Knoten einmal betrachtes.

 

[mihe7]

Pass aber auf, dass Du nur Vergleichbares miteinander vergleichst. Sollte z. B. etwas mit "externem Speicher" drankommen, interessieren bei der Laufzeit in der Regel nur die externen Zugriffe.

 

[LimDul]

Bezüglich wie oft wird die Queue durchlaufen (Also die Schleife in Zeile 5): Nun, dafür musst du den Algorithmus verstehen. Wichtig ist hier von konkreten Eingaben zu abstrahieren und obere Grenzen anzugeben. Offensichtlich, wenn ich einen Graphen reingebe der nur aus Knoten ohne Kanten bestehe, ist der Algorithmus sehr schnell zu ende. Frage die du dir stellen kannst:
- Welche Art von Elementen enthält die Queue?
- Wie viele Elemente werden pro Durchlauf mindestens entfernt
- Können Elemente, die einmal drin waren nochmal hinzugefügt werden?
- Wenn nein, dann sollte die Frage jetzt recht einfach beantwortbar sein.
- Wenn ja, wird es komplex, weil dann muss tiefer reinschauen und das weiter aufdröseln.

 

[Kirby.exe]

Danke für die Tipps ich werde mal mein Glück versuchen und die Laufzeit ausrechnen