Effizienz von Algorithmen: Ressourcenverbrauch verstehen 🚀

Programme können unterschiedlich effizient sein, d.h. zur Lösung ihrer Aufgabe unterschiedliche viele Ressourcen (wie Laufzeit, Speicherplatz, Netzwerklast, usw.) verbrauchen. Wie aber kann man die Effizient von Algorithmen definieren, die ja - anders als Programme - nur als Idee existieren? In diesem Video werden grundlegende Ideen und Begriffe zu dieser Frage vorgestellt. Am Ende kommen wir zu der Idee der asymptotischen Laufzeitabschätzung, um die es dann im nächsten Video gehen wird (https://youtu.be/D8n5qnyFIKc).

00:00 - Intro
00:19 - Korrektheit vs. Effizienz
01:36 - Beispiele
07:03 - Eingabegröße n
10:16 - best-case vs. worst-case
13:33 - warum worst-case interessanter ist
16:25 - quadratische Laufzeit
23:55 - Laufzeiten vergleichen

- Asymptotische Laufzeitabschätzung ("Großes O"): https://youtu.be/D8n5qnyFIKc
- Laufzeiten bestimmen: https://youtu.be/U0RXz0llOpY

Weiterführende Videos:
- Average-Case Analyse bei randomisierten Algorithmen: https://youtu.be/xZo9GkzhZWE
- Amortisierte Kostenanalyse am Beispiel der ArrayList: https://youtu.be/162rT8stfE0