Big-O-Notation: Was ist das und warum ist es wichtig?

Das macht Spaß! Die Kommunikation mit Big O ist einer der ersten überraschenden Übergänge für junge Entwickler.

Schauen wir uns an, warum.

Aber zuerst ein Boxenstopp. Erinnern Sie sich an diese absolut lächerlichen Wortaufgaben aus der Grundschule?

Sally ging zum Lebensmittelladen und kaufte 37 Wassermelonen. Sie hatte 20 Dollar. Jede Wassermelone kostet 0,70 $. Wie viel Geld hat Sally, wenn sie nach Hause kommt?

Haben Sie sich gefragt: „Wie um alles in der Welt soll Sally nach Hause kommen? Mit 37 Wassermelonen?! 6,00 $ werden nicht ausreichen, um ein Uber mit genügend Platz für die Melonen zu bekommen … was macht Sally?!“

Dumme Sally.

Manche Leute sagen, dass dadurch der Wald vor lauter Bäumen verloren geht. Ich sage, es ist einfach eine furchtbar faule Art, Übungsaufgaben zu konstruieren.

Der Zweck von Big O Notation besteht darin, mit anderen Menschen über die Qualität unseres Handwerks sprechen, sprichwörtlich kommunizieren zu können. Der besondere Fokus liegt hier darauf, den Vergleich zwischen Lösungen im Worst-Case-Szenario mit zunehmender Eingabegröße zu ermöglichen.

Wir möchten in der Lage sein, abstrakt über mögliche Lösungen zu sprechen ( dasselbe, als würde man sagen: Algorithmen ). Das ist ein entscheidender Punkt: abstrakt . Die Daten, die wir haben , sind uns völlig egal . Wenn wir mit diesen Ideen spielen, gehen wir von einem theoretisch gigantischen, aber endlichen Datensatz aus.

Wenn wir über die Daten nachdenken, die wir haben , handelt es sich dabei um konkrete Überlegungen. Wenn wir an die Big-O-Notation denken, denken wir abstrakt. Es ist EINFACH, auf konkrete Argumente zurückzugreifen. Hier verbringen wir den Großteil unseres Lebens. Es ist einfach, normalerweise offensichtlich und bequem.

Soll ich jetzt die Straße überqueren? Gibt es ein Auto? NEIN? Okay, ärgere dich.

Tun Sie es nicht, wenn Sie abstrakt denken!

Definitionen, schnell

Stört es Sie, wenn ich Ihnen hier einen Gefallen tue? Es gibt eine Reihe mathematischer Begriffe, die ebenfalls im Weg sein könnten. Hier ist eine visuelle Darstellung einiger gebräuchlicher Big-O-Begriffe, geordnet vom besten zum schlechtesten Fall. Wir brauchen diese, damit wir nachdenken und lernen können, anstatt uns auf die Terminologie zu beschränken.

O(1) – „Konstante Zeit“

Dabei spielt es keine Rolle, wie groß die Eingabe ist, das System liefert das Ergebnis immer in der gleichen Zeit zurück.

O(log n) – „Protokollzeit“

Während die Lösung (oder der Algorithmus) die Eingabe durchläuft, wird jede Iteration schneller!

O(n) – „Lineare Zeit“

Während der Algorithmus iteriert, dauert jede Iteration genauso lange wie die vorherige Iteration.

O(n log n) – hier gibt es keine ausgefallene Terminologie

Zeigt, dass die Ideen kombiniert werden können (huch). Während wir iterieren, wird jede Iteration langsamer, aber ziemlich langsam langsamer.

O(n^2) – „n im Quadrat“

Mit jeder Iteration werden die Iterationen ziemlich schnell langsamer.

O(n!) – „n Fakultät“

Mit jeder Iteration werden die Iterationen superschnell langsamer.

Das Ziel besteht darin, sich so weit wie möglich von „n-faktoriell“ fernzuhalten und nicht viel schlechter als Constant zu werden.

Nachdem wir das alles verstanden haben, versuchen wir nun, die Lücke zu schließen.

Überbrückung der Lücke zwischen konkretem und abstraktem Denken

Big-O-Notation verstehen

Die Big-O-Notation wird verwendet, um die Leistung oder Komplexität eines Algorithmus (Lösung) zu beschreiben. Es bietet ein umfassendes Verständnis dafür, wie sich ein Algorithmus (eine Lösung) verhält, wenn die Größe der Eingabe zunimmt.

Beispielsweise erhöht sich die Laufzeit eines Algorithmus mit der Komplexität O(n) linear mit der Größe der Eingabe.

Konkretes vs. abstraktes Denken

Die Herausforderung entsteht, wenn Entwickler Überlegungen zu bestimmten Daten mit Überlegungen zum Algorithmus selbst verwechseln. Sätze wie „Aber diese Daten sind echt“ können auf diese Verwirrung hinweisen.

Auch wenn Überlegungen zu den realen Daten Ihnen den Einstieg erleichtern können, ist es wichtig, die Lösung von der aktuellen Eingabe zu trennen.

Warum das Missverständnis?

Frühe Berufseinsteiger könnten diesen Fehler machen, weil sie keine Erfahrung mit größeren Problemen haben oder zu sehr in die Besonderheiten eines aktuellen Problems vertieft sind. Um skalierbare Lösungen zu schaffen, ist es wichtig, die konkreten Details von der abstrakten Komplexität zu trennen.

Praktische Konsequenzen

Was passiert mit dem Algorithmus, wenn die Eingabe um das 100- oder 100.000-fache steigt? Eine unglaublich komplexe Lösung könnte bei einem größeren Datensatz auseinanderfallen.

Ein Algorithmus, der für kleine Datensätze in Ordnung zu sein scheint, kann bei größeren Datensätzen dramatisch versagen, was zu Leistungsproblemen und anderen Herausforderungen führt.

Lernen, abstrakt zu denken

Die Entwicklung der Fähigkeit, abstrakt über Probleme nachzudenken, erfordert Übung und Anleitung. Einige Strategien umfassen:

• Abstrakte Modelle erstellen : Probleme verallgemeinernd darstellen.

• Algorithmen getrennt von Daten analysieren : Bewerten, wie sich der Algorithmus unabhängig von bestimmten Datenpunkten verhält.

• Erstellen von Skalierungsszenarien : Stellen Sie sich vor, wie sich der Algorithmus bei unterschiedlichen Eingabegrößen verhält.

Abstraktes Denken im Allgemeinen und die Big-O-Notation im Besonderen sind wesentliche Fähigkeiten im Algorithmus-Design – mit anderen Worten, eine Lösung für ein Problem zu finden.

Indem Entwickler lernen, die Problemkomplexität von der Algorithmuskomplexität zu trennen, können sie häufige Fallstricke vermeiden und ihre Problemlösungsfähigkeiten verbessern, wenn sie alleine arbeiten. Außerdem können sie ihre Fähigkeit, mit anderen Leuten zusammenzuarbeiten, die ebenfalls die Zeit investiert haben, um zu lernen, wie man auf diese Weise kommuniziert, erheblich verbessern.

Komplexe Probleme erfordern oft keine komplexen Lösungen . (Sally brauchte wahrscheinlich gar keine 37 Wassermelonen … was macht sie mit 37 Wassermelonen?!)