Big-O-Notation Erklärt mit Code-Beispielen
Ein Zugriff auf ein Python-Dictionary dauert etwa 100 Nanosekunden, egal ob das Dictionary 1.000 oder 1.000.000 Schlüssel enthält. Eine verschachtelte Schleife, die eine Liste auf Duplikate prüft, braucht eine halbe Millisekunde bei 200 Elementen und 136 Millisekunden bei 3.200. Sechzehnmal die Eingabe, fast 280-mal die Wartezeit. Gleiche Maschine, gleiches Python. Die Big-O-Notation ist der Name für diesen Unterschied. Was die Big-O-Notation misst Big O beschreibt, wie die Laufzeit (oder der Speicherverbrauch) eines Codestücks wächst, wenn die Eingabe größer wird. Es ist keine Stoppuhr-Messung, und es ist egal, ob Ihr Laptop schnell oder langsam ist. Entscheidend ist die Form der Wachstumskurve: Verdoppelt sich die Zeit, wenn Sie die Eingabe verdoppeln, vervierfacht sie sich, oder bewegt sie sich kaum? ...