Alles, was Sie über „Big O Notation“ wissen müssen, um Ihr nächstes Coding-Interview zu knacken

Im Rahmen meiner Softwareentwicklungsausbildung musste ich Fähigkeiten in verschiedenen Bereichen aufbauen, um mich vollständig auf meine erste Softwareposition vorzubereiten. Und jedes Software-Schulungsprogramm, das sein Geld wert ist, wird einen angemessenen Teil des Lehrplans enthalten, der darauf ausgerichtet ist, sich auf das berüchtigte Coding-Interview vorzubereiten.

Zu diesem Zweck arbeite ich zu Beginn eines jeden Tages an der Lösung von Algorithmen, da dies ein Hauptteil (und für viele der schwierigste Teil ) der meisten Codierungsinterviews ist.

Eine Sache, auf die ich bei der Arbeit an Informatik-Algorithmen gestoßen bin, ist die sogenannte „Big O-Notation“ .

Es ist ein ziemlich abstraktes und sehr esoterisches Konzept, von dem die überwiegende Mehrheit der Menschen niemals etwas hören oder sich darum kümmern wird. ABER es ist bekannt als eine häufig gestellte Frage zum Codierungsinterview , und deshalb ist es eines der Dinge, über die ich einige Zeit gelernt habe.

Was du wissen musst

Folgendes habe ich aufgenommen, um mich vorzubereiten

Um die Szene für „Big O“ zu setzen, müssen wir zunächst anerkennen, dass Software natürlich stark auf Daten basiert . Riesige Datenberge. Und diese Daten zu nutzen, ist das Ziel der Codierung. Damit ein Programm Daten verwenden kann, muss es häufig zunächst diese Daten in einer logischen Reihenfolge sortieren. Ob das alphabetisch, chronologisch, nach Größe, nach Datum usw. ist.

Das Sortieren erfolgt STÄNDIG und macht tatsächlich einen großen Teil aller Computer- und Internetaktivitäten aus. Ich habe Programmierer sagen hören, dass "Quick Sort so ziemlich das ist, was das ganze Internet ausführt".

Was meinen sie damit? Das Sortieren von Daten ist ein eigener Unterabschnitt innerhalb des Informatikstudiums, und es gibt viele genau definierte Algorithmen zum Sortieren. Es gibt schnelle Sortierung, Blasensortierung, Auswahlsortierung, Zusammenführungssortierung, Heap-Sortierung und vieles mehr. Jeder mit unterschiedlichen Ansätzen, um zu den gleichen oder ähnlichen Ergebnissen zu gelangen.

Aber welches ist am besten, wenn sie (fast) alle das gleiche Ergebnis liefern?

Am besten bedeutet normalerweise, welches am schnellsten ist. Hier kam „Big O“ ins Spiel.

Die Big O-Notation, manchmal auch als „asymptotische Analyse“ bezeichnet, untersucht in erster Linie, wie viele Operationen ein Sortieralgorithmus benötigt, um eine sehr große Sammlung von Daten vollständig zu sortieren. Dies ist ein Maß für die Effizienz und so können Sie einen Algorithmus direkt mit einem anderen vergleichen.

Wenn Sie eine einfache App mit nur wenigen zu bearbeitenden Daten erstellen, ist diese Art der Analyse nicht erforderlich. Wenn Sie jedoch mit sehr großen Datenmengen arbeiten, z. B. einer Social-Media-Site oder einer großen E-Commerce-Site mit vielen Kunden und Produkten, können kleine Unterschiede zwischen den Algorithmen erheblich sein.

Die Big O-Notation bewertet die Effizienz eines Algorithmus

Dies geschieht in Bezug auf " O " und " n " (Beispiel: " O (log n)") , wobei

  • O bezieht sich auf die Reihenfolge der Funktion oder ihre Wachstumsrate und
  • n ist die Länge des zu sortierenden Arrays.

Lassen Sie uns ein Beispiel durcharbeiten. Wenn ein Algorithmus die Anzahl der erforderlichen Operationen hat, lautet die Formel:

f (n) = 6n ^ 4 - 2n ^ 3 + 5

Wenn sich „ n “ der Unendlichkeit nähert (für sehr große Datenmengen), ist von den drei vorhandenen Begriffen 6n ^ 4 der einzige, der zählt. Die kleineren Begriffe 2n ^ 3 und 5 werden also eigentlich einfach weggelassen, weil sie unbedeutend sind. Gleiches gilt eigentlich für die „ 6 “ in 6n ^ 4 .

Daher hätte diese Funktion eine Auftragswachstumsrate oder ein "großes O" -Rating von O (n ^ 4).

Wenn Sie sich viele der am häufigsten verwendeten Sortieralgorithmen ansehen,Die Bewertung von O (n log n) ist im Allgemeinen die beste, die erreicht werden kann. Zu den Algorithmen, die mit dieser Bewertung ausgeführt werden, gehören Schnellsortierung, Heap-Sortierung und Zusammenführungssortierung. Die schnelle Sortierung ist der Standard und wird in fast allen Softwaresprachen standardmäßig verwendet.

Es ist wichtig zu beachten, dass es keinen einzigen Algorithmus gibt, der in allen Fällen am schnellsten ist , da Daten auf alle Arten von Zuständen in ein Programm eingegeben werden können. Und die Ansätze jedes Algorithmus haben ein Best-Case- und ein Worst-Case-Szenario, in denen sie ihre beste oder schlechteste Leistung erbringen.

Während Quick Sort der Standard ist, konkurriert es auch mit Merge Sort und Heap Sort, anderen Sortieralgorithmen mit O (n log n). Es gibt Szenarien, in denen diese stattdessen verwendet werden.

Der direkteste Konkurrent von Quick Sort ist Heap Sort. Die Laufzeit von Heap Sort beträgt ebenfalls O (n log n), aber die durchschnittliche Laufzeit von Heap Sort wird normalerweise als langsamer angesehen als die direkte Schnellsortierung.

Die Zusammenführungssortierung ist eine stabile Sortierung , dh sie behält die Eingabereihenfolge gleicher Elemente in der Ausgabe bei, im Gegensatz zur standardmäßigen direkten schnellen Sortierung und Heap-Sortierung.

Bubble / Insertion / Selection Sort-Lauf bei O (n²) , was in Bezug auf die Anzahl der Operationen erheblich länger dauern kann als die oben aufgeführten, die bei O (n log n) bewertet wurden, wenn es sich um wirklich große Datenmengen handelt. Es kann jedoch Szenarien geben, in denen die anderen je nach Daten schneller sind.

Es gibt auch Zeiten, in denen etwas sehr Einfaches wie das Zählen der Sortierung großartig ist, weil es viel schneller zu schreiben und viel einfacher zu visualisieren und zu verstehen ist.

Manchmal müssen Sie nicht nur die Zeitanforderungen eines Algorithmus berücksichtigen, sondern auch die Datenraumanforderungen (oder vielleicht sogar noch mehr). Einige Algorithmen arbeiten auch mit einem geringeren Speicherbedarf.

Warum müssen Sie das alles wissen?

Wenn Sie also immer nur auf den integrierten Sortieralgorithmus einer Sprache zurückgreifen (der auf Quick Sort basiert), warum sollten Sie sich dann für Sortieralgorithmen und „Big O“ interessieren? Warum sollten Unternehmen Sie in einem Interview danach fragen?

Die Antwort ist, dass Sie durch das Studium der Big O-Notation das sehr wichtige Konzept der Effizienz in Ihrem Code verstehen. Wenn Sie also mit großen Datenmengen arbeiten, wissen Sie genau, wo größere Verlangsamungen zu Engpässen führen können und wo mehr Aufmerksamkeit geschenkt werden sollte, um die größten Verbesserungen zu erzielen. Dies wird auch als Sensitivitätsanalyse bezeichnet und ist ein wichtiger Bestandteil beim Lösen von Problemen und beim Schreiben großartiger Software.

Wenn Sie also versuchen, sich auf Ihr erstes Interview vorzubereiten, oder wenn Sie in Ihrem letzten Interview Probleme hatten, können Sie Ihr Wissen über Konzepte wie Big O Notation und andere Informatik-Themen erweitern. Sie sind besser gerüstet, um Ihr Potenzial zu demonstrieren und zu beeindrucken, um diese Position zu erreichen.