Über Komplexität nachdenken, bevor optimiert wird

Ziel

Im Review Code erkennen, dessen Kosten schneller wachsen als seine Eingabe, und Datenstrukturen wählen, deren dokumentierte Komplexität zum Zugriffsmuster passt.

Voraussetzungen

Kenntnis der Kosten von Container-Operationen in der verwendeten Sprache (Pythons Wiki listet sie auf: list append amortisiert O(1), x in list O(n), dict- und set-Zugehörigkeit im Mittel O(1)).

Schritte

1. Bei jeder Schleife fragen, was der Rumpf kostet: ein Zugehörigkeitstest auf einer Liste innerhalb einer Schleife über eine andere Liste ist O(n·m); die innere Liste in ein set umwandeln.
2. Nach wiederholter Arbeit suchen: eine Summe neu berechnen oder innerhalb einer Schleife neu sortieren; das herausziehen oder inkrementell pflegen.
3. Das Zusammenbauen von Strings prüfen: wiederholtes += in einer Schleife kann quadratisch sein; Teile sammeln und einmal zusammenfügen.
4. Rekursion und Queues begrenzen; unbeschränktes Wachstum mit der Eingabe ist ein Denial-of-Service-Pfad.
5. Mit realistischen Grössen abschätzen: n = 10⁵ macht O(n²) ≈ 10¹⁰ Operationen, das sind Minuten, nicht Millisekunden.
6. Nur dort mit einem Profil bestätigen, wo die Schätzung unklar ist oder die konstanten Faktoren eine Rolle spielen.

Erwartetes Ergebnis

Reviews erkennen den quadratischen Pfad, bevor er in Produktion gelangt; Datenstrukturen werden für die tatsächlich ausgeführten Operationen gewählt.

Grenzen und Prüfbasis

Big-O verbirgt Konstanten und Cache-Effekte; ein linearer Scan einer kleinen Liste schlägt einen Hash-Lookup. Amortisierte Schranken können teure Einzeloperationen enthalten. Die Kostentabelle folgt der zitierten Wiki-Seite; die Methode ist gängige Praxis.