Warum Algorithmen analysieren?
Wachstumsrate der Laufzeit oder Speicherbedarf eines Algorithmus je nach Eingabe.
Wie ermittelt man die relative Leistung von Algorithmen?
Untersuchung von langfristigem Verhalten für grosse Eingaben
Was ist der Best-Case?
Wie viele Schritte minimal nötig sind
Was ist der Worst-Case?
Wie viele Schritte maximal nötig sein können
Von was ist der Worst-Case primär abhängig?
Von der Länge n der Liste (input)
Was ist die Schwierigkeit, weshalb man die Asymptotische Analyse nutzt?
Zählen der genauen Anzahl Rechnungsschritt eines Algorithmus ist nicht immer einfach.
Was macht man bei der Asymptotischen Analyse?
Algorithmen in Klassen mit unterschiedlichen Rechenzeitkomplexität oder Speicherplatzkomplexität einteilen.
Welche Notationen gibt es?
- Big-O Notation
- Big-Ω Notation
- Big-Θ Notation
Was ist die Big-O Notation
f wächst nicht stärker als g
Was ist die Big-Ω Notation
f wächst nicht langsamer als g
Was ist die Big-Θ Notation
f wächst asymptotisch gleich wie g
Defintion Big-O Notation
Definition Big-Ω Notation
Definition Big-Θ Notation
Mit welcher Notation können die wichtigsten Komplexitätsklassen beschrieben werden?
Big-O Notation
Was ist polynominelles Wachstum und wie nennt man Probleme, welche man mit so einem Algorithmus lösen kann?
real lösbar
Was ist ein exponentielles Wachstum und wie nennt man Probleme, welche nur mit solchen Algorithmen gelöst werden können?
real unlösbar
