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 von besteht darin, mit anderen über die Qualität unseres Handwerks sprechen, sprichwörtlich zu können. Der besondere Fokus liegt hier darauf, den Vergleich zwischen Lösungen mit zunehmender Eingabegröße zu ermöglichen. Zweck Big O Notation Menschen kommunizieren im Worst-Case-Szenario Wir möchten in der Lage sein, abstrakt über mögliche Lösungen zu sprechen ( ). Das ist ein entscheidender Punkt: . Die Daten, die wir , sind uns . Wenn wir mit diesen Ideen spielen, gehen wir von einem theoretisch gigantischen, aber endlichen Datensatz aus. dasselbe, als würde man sagen: Algorithmen abstrakt haben völlig egal Wenn wir über die Daten nachdenken, die wir , 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. haben 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: : Probleme verallgemeinernd darstellen. Abstrakte Modelle erstellen : Bewerten, wie sich der Algorithmus unabhängig von bestimmten Datenpunkten verhält. Algorithmen getrennt von Daten analysieren : Stellen Sie sich vor, wie sich der Algorithmus bei unterschiedlichen Eingabegrößen verhält. Erstellen von Skalierungsszenarien 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, von 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. die Problemkomplexität der Algorithmuskomplexität Komplexe erfordern oft keine komplexen . (Sally brauchte wahrscheinlich gar keine 37 Wassermelonen … was macht sie mit 37 Wassermelonen?!) Probleme Lösungen
