Aufgaben zum Laufzeitaufwand von Algorithmen

Beim Selection Sort wird ein Array sortiert, indem zunächst ein zweites, gleich großes Array angelegt wird. Anschließend wird immer wieder nach dem kleinsten Element im Ausgangsarray gesucht, es wird aus diesem entfernt und an die nächste Stelle des Zielarrays kopiert.

• a) Wie oft ist das "Durchlaufen" des Quellarrays im best case, average case und worst case nötig?
• b) Wie viele Vergleiche sind bei jedem Durchlaufen/insgesamt in den drei Fällen nötig?
• c) Geben Sie die Komplexitätsklasse des Algorithmus im best case, average case und worst case an.

In einem Graphen mit $n$ Knoten und durchschnittlich $k$ Kanten, die vom Knoten wegweisen, soll ein Weg zwischen zwei Kanten mittels Tiefensuche gesucht werden.

• a) Begründen Sie, weshalb die Anzahl der Schritte im innersten Teil des Algorithmus proportional zu $a^n$ ist.
• b) Welche Komplexitätsklasse hat demnach der Algorithmus?