Algorithmus-Komplexität

Question 1

Warum kann man die Laufzeit nicht einfach stoppen

Answer 1

vom Rechner und technischer Entwicklung abhängig

Question 2

Was beschriebt die O-Notation

Answer 2

Komplexitätsklasse / Größenordnung der Schrittzahlen eines Algorithmus in Abhängigkeit von Problemgröße

Question 3

Welche Komplexitätsklasse gibt es

Answer 3

O(1) -> konstanter Aufwand
O(log n) -> logarithm. Aufw.
O(n) -> linearer Aufw.
O(n * log n) -> linear-log. Aufw.
O(n^2) -> quadratischer Aufw.
O(n^k) -> polynomialer Aufw.
O(k^n) -> exponentieller Aufw.

Question 4

Bedingung für Feststellung der Komplexitätsklasse

Answer 4

f(n) fällt in O(g(n)) wenn
c (positive reelle Zahl)
n0 (natürliche Zahl)
existieren, für die gilt
f(n) <= c*g(n)
für alle n >= n0

Question 5

Laufzeit einer einfachen for-Schleife

Answer 5

größtmögliche Iterationzeit * Anzahl der Iterationen

Question 6

Laufzeit verschachtelten for Schleife

Answer 6

Laufzeit innere Schleife ∗ Produkt(äußeren Schleifengrößen)

Question 7

Laufzeit if-else-Anweisung

Answer 7

Testaufwand + max⁡(True-Aufwand, False-Aufwand)

Question 8

Komplexitätsklasse Nacheinanderausführung

Answer 8

Komplexitätsklasse entspricht dem Teil mit dem größten Exponenten (weil sich dieser am schnellsten erhöht) konstante Faktoren werden ignoriert