Big-O als Nachschlagewerk für Datenstrukturen
Zusammenfassung
Eric Rowell vergleicht Laufzeit und Speicherbedarf verbreiteter Datenstrukturen sowie Sortieralgorithmen in einer kompakten Übersicht.
Ideen
- Big-O beschreibt Wachstum bei zunehmender Eingabegröße.
- Arrays und Listen tauschen Zugriffsgeschwindigkeit gegen flexible Änderungen.
- Hashtabellen bieten erwarteten konstanten Zugriff unter guten Annahmen.
- Sortierverfahren unterscheiden sich bei Zeit, Speicher und Stabilität.
Einsichten
- Asymptotik vergleicht Wachstum, nicht reale Laufzeit kleiner Eingaben.
- Durchschnittswerte können gefährliche schlechteste Fälle verdecken.
- Datenstrukturwahl folgt tatsächlichen Operationen statt Gewohnheit.
Fakten
- Die Übersicht enthält Such-, Einfüge- und Löschkosten.
- Mehrere Sortieralgorithmen werden grafisch verglichen.
- Auch Speicherkomplexität wird ausgewiesen.
Empfehlungen
- Miss Eingabegrößen und Operationsmischung des echten Systems.
- Prüfe Annahmen hinter durchschnittlichen Laufzeiten.
Referenzen
Der Link zur Originalquelle öffnet einen neuen Tab.