Algorithmische Komplexität

Hallo! Die heutige Lektion wird etwas anders sein als die anderen. Der Unterschied besteht darin, dass es nur indirekt mit Java zusammenhängt. Allerdings ist dieses Thema für jeden Programmierer sehr wichtig. Wir werden über Algorithmen sprechen . Was ist ein Algorithmus? Einfach ausgedrückt handelt es sich um eine Abfolge von Aktionen, die ausgeführt werden müssen, um das gewünschte Ergebnis zu erzielen . Im Alltag nutzen wir häufig Algorithmen. Zum Beispiel haben Sie jeden Morgen eine bestimmte Aufgabe: zur Schule oder zur Arbeit gehen und gleichzeitig sein:

• Bekleidet
• Sauber
• gefüttert

Mit welchem ​​Algorithmus können Sie dieses Ergebnis erzielen?

1. Wachen Sie mit einem Wecker auf.
2. Duschen Sie und waschen Sie sich.
3. Bereiten Sie Frühstück und Kaffee oder Tee zu.
4. Essen.
5. Wenn Sie Ihre Kleidung am Vorabend nicht gebügelt haben, dann bügeln Sie sie.
6. Sich anziehen.
7. Das Haus verlassen.

Mit dieser Abfolge von Aktionen erzielen Sie auf jeden Fall das gewünschte Ergebnis. Beim Programmieren arbeiten wir ständig daran, Aufgaben zu erledigen. Ein erheblicher Teil dieser Aufgaben kann mit bereits bekannten Algorithmen erledigt werden. Angenommen, Ihre Aufgabe besteht beispielsweise darin, eine Liste mit 100 Namen in einem Array zu sortieren . Diese Aufgabe ist recht einfach, kann aber auf unterschiedliche Weise gelöst werden. Hier ist eine mögliche Lösung: Algorithmus zum alphabetischen Sortieren von Namen:

1. Kaufen oder laden Sie die Ausgabe von Webster's Third New International Dictionary aus dem Jahr 1961 herunter.
2. Finden Sie jeden Namen aus unserer Liste in diesem Wörterbuch.
3. Schreiben Sie auf ein Blatt Papier die Seite des Wörterbuchs, auf der sich der Name befindet.
4. Verwenden Sie die Zettel, um die Namen zu sortieren.

Wird eine solche Abfolge von Aktionen unsere Aufgabe erfüllen? Ja, das wird es sicherlich. Ist diese Lösung effizient ? Kaum. Hier kommen wir zu einem weiteren sehr wichtigen Aspekt von Algorithmen: ihrer Effizienz . Es gibt mehrere Möglichkeiten, diese Aufgabe zu erfüllen. Aber sowohl beim Programmieren als auch im Alltag wollen wir den effizientesten Weg wählen. Wenn Ihre Aufgabe darin besteht, ein mit Butter bestrichenes Stück Toast zuzubereiten, könnten Sie damit beginnen, Weizen zu säen und eine Kuh zu melken. Aber das wäre ineffizientLösung – es wird viel Zeit in Anspruch nehmen und viel Geld kosten. Sie können Ihre einfache Aufgabe erfüllen, indem Sie einfach Brot und Butter kaufen. Obwohl Sie damit das Problem lösen können, ist der Algorithmus, der Weizen und eine Kuh einbezieht, zu komplex, um ihn in der Praxis anzuwenden. In der Programmierung verwenden wir eine spezielle Notation namens Big-O-Notation , um die Komplexität von Algorithmen zu beurteilen. Mit Big O lässt sich abschätzen, wie stark die Ausführungszeit eines Algorithmus von der Größe der Eingabedaten abhängt . Schauen wir uns das einfachste Beispiel an: die Datenübertragung. Stellen Sie sich vor, Sie müssen einige Informationen in Form einer Datei über eine große Entfernung (z. B. 5.000 Meilen) senden. Welcher Algorithmus wäre am effizientesten? Das hängt von den Daten ab, mit denen Sie arbeiten. Angenommen, wir haben eine Audiodatei mit einer Größe von 10 MB. In diesem Fall besteht der effizienteste Algorithmus darin, die Datei über das Internet zu senden. Es konnte nicht länger als ein paar Minuten dauern! Lassen Sie uns unseren Algorithmus noch einmal formulieren: „Wenn Sie Informationen in Form von Dateien über eine Entfernung von 5.000 Meilen übertragen möchten, sollten Sie die Daten über das Internet senden.“ Exzellent. Jetzt analysieren wir es. Erfüllt es unsere Aufgabe?Nun ja, das tut es. Aber was können wir über seine Komplexität sagen? Hmm, jetzt wird es interessanter. Tatsache ist, dass unser Algorithmus stark von den Eingabedaten abhängt, nämlich der Größe der Dateien. Wenn wir 10 Megabyte haben, ist alles in Ordnung. Was aber, wenn wir 500 Megabyte senden müssen? 20 Gigabyte? 500 Terabyte? 30 Petabyte? Wird unser Algorithmus nicht mehr funktionieren? Nein, alle diese Datenmengen können tatsächlich übertragen werden. Wird es länger dauern? Ja, es wird! Jetzt kennen wir ein wichtiges Merkmal unseres Algorithmus: Je größer die zu sendende Datenmenge, desto länger dauert die Ausführung des Algorithmus. Wir möchten diesen Zusammenhang (zwischen der Größe der Eingabedaten und der zum Senden erforderlichen Zeit) jedoch genauer verstehen. In unserem Fall ist die algorithmische Komplexität linear . „Linear“ bedeutet, dass mit zunehmender Menge der Eingabedaten die Zeit, die zum Senden benötigt wird, ungefähr proportional zunimmt. Wenn sich die Datenmenge verdoppelt, verdoppelt sich auch die für den Versand benötigte Zeit. Wenn sich die Daten um das Zehnfache erhöhen, erhöht sich die Übertragungszeit um das Zehnfache. Unter Verwendung der Big-O-Notation wird die Komplexität unseres Algorithmus als O(n) ausgedrückt.. Diese Notation sollten Sie sich für die Zukunft merken – sie wird immer für Algorithmen mit linearer Komplexität verwendet. Beachten Sie, dass wir hier nicht über verschiedene Dinge sprechen, die variieren können: Internetgeschwindigkeit, Rechenleistung unseres Computers usw. Bei der Beurteilung der Komplexität eines Algorithmus macht es einfach keinen Sinn, diese Faktoren zu berücksichtigen – sie liegen auf jeden Fall außerhalb unserer Kontrolle. Die Big-O-Notation drückt die Komplexität des Algorithmus selbst aus, nicht die „Umgebung“, in der er ausgeführt wird. Fahren wir mit unserem Beispiel fort. Angenommen, wir erfahren letztendlich, dass wir Dateien mit einer Gesamtgröße von 800 Terabyte senden müssen. Wir können unsere Aufgabe natürlich auch dadurch erfüllen, dass wir sie über das Internet versenden. Es gibt nur ein Problem: Bei haushaltsüblichen Datenübertragungsraten (100 Megabit pro Sekunde) dauert es etwa 708 Tage. Fast 2 Jahren! :O Unser Algorithmus passt hier offensichtlich nicht gut. Wir brauchen eine andere Lösung! Unerwartet kommt uns der IT-Riese Amazon zu Hilfe! Mit dem Snowmobile-Dienst von Amazon können wir große Datenmengen auf einen mobilen Speicher hochladen und diese dann per LKW an die gewünschte Adresse liefern! Wir haben also einen neuen Algorithmus! „Wenn Sie Informationen in Form von Dateien über eine Entfernung von 5.000 Meilen übertragen möchten und der Versand über das Internet mehr als 14 Tage dauern würde, sollten Sie die Daten mit einem Amazon-Lkw versenden.“ Wir haben hier willkürlich 14 Tage gewählt. Nehmen wir an, das ist die längste Zeit, die wir warten können. Lassen Sie uns unseren Algorithmus analysieren. Wie sieht es mit seiner Geschwindigkeit aus? Selbst wenn der Lkw nur 50 Meilen pro Stunde fährt, legt er 5.000 Meilen in nur 100 Stunden zurück. Das sind etwas mehr als vier Tage! Das ist deutlich besser als die Möglichkeit, die Daten über das Internet zu versenden. Und wie sieht es mit der Komplexität dieses Algorithmus aus? Ist es auch linear, also O(n)? Nein ist es nicht. Denn dem LKW ist es egal, wie schwer man ihn belädt – er fährt immer noch ungefähr mit der gleichen Geschwindigkeit und kommt pünktlich an. Egal, ob wir 800 Terabyte oder das Zehnfache haben, der LKW erreicht sein Ziel immer noch innerhalb von 5 Tagen. Mit anderen Worten: Der LKW-basierte Datenübertragungsalgorithmus weist eine konstante Komplexität auf. „Konstant“ bedeutet hier, dass es nicht von der Größe der Eingabedaten abhängt. Legen Sie ein 1-GB-Flash-Laufwerk in den LKW, es wird innerhalb von 5 Tagen eintreffen. Legen Sie Datenträger mit 800 Terabyte an Daten ein, die Lieferung erfolgt innerhalb von 5 Tagen. Bei Verwendung der Big-O-Notation wird konstante Komplexität durch O(1) bezeichnet . Wir haben uns mit O(n) und O(1) vertraut gemacht, also schauen wir uns nun weitere Beispiele aus der Welt der Programmierung an :) Angenommen, Sie erhalten ein Array mit 100 Zahlen und die Aufgabe besteht darin, jede davon anzuzeigen die Konsole. Sie schreiben eine gewöhnliche forSchleife, die diese Aufgabe ausführt

int[] numbers = new int[100];
// ...fill the array with numbers

for (int i: numbers) {
   System.out.println(i);
}

Wie komplex ist dieser Algorithmus? Linear, also O(n). Die Anzahl der Aktionen, die das Programm ausführen muss, hängt davon ab, wie viele Zahlen ihm übergeben werden. Wenn das Array 100 Zahlen enthält, gibt es 100 Aktionen (Anweisungen zum Anzeigen von Zeichenfolgen auf dem Bildschirm). Wenn das Array 10.000 Zahlen enthält, müssen 10.000 Aktionen ausgeführt werden. Kann unser Algorithmus in irgendeiner Weise verbessert werden? Nein. Egal was passiert, wir müssen N Durchgänge durch das Array durchführen und N Anweisungen ausführen, um Strings auf der Konsole anzuzeigen. Betrachten Sie ein anderes Beispiel.

public static void main(String[] args) {

   LinkedList<Integer> numbers = new LinkedList<>();
   numbers.add(0, 20202);
   numbers.add(0, 123);
   numbers.add(0, 8283);
}

Wir haben ein Leerzeichen LinkedList, in das wir mehrere Zahlen einfügen. Wir müssen die algorithmische Komplexität des Einfügens einer einzelnen Zahl in LinkedListunser Beispiel bewerten und wie sie von der Anzahl der Elemente in der Liste abhängt. Die Antwort ist O(1), also konstante Komplexität . Warum? Beachten Sie, dass wir jede Zahl am Anfang der Liste einfügen. Darüber hinaus werden Sie sich daran erinnern, dass sich LinkedListdie Elemente nirgendwo verschieben, wenn Sie eine Zahl in eine einfügen. Die Links (oder Referenzen) werden aktualisiert (wenn Sie vergessen haben, wie LinkedList funktioniert, schauen Sie sich eine unserer alten Lektionen an ). Wenn die erste Zahl in unserer Liste ist xund wir die Zahl y am Anfang der Liste einfügen, müssen wir nur Folgendes tun:

x.previous  = y;
y.previous = null;
y.next = x;

Wenn wir die Links aktualisieren, ist es uns egal, wie viele Zahlen bereits darin enthalten sindLinkedList , ob eine oder eine Milliarde. Die Komplexität des Algorithmus ist konstant, also O(1).

Logarithmische Komplexität

Keine Panik! :) :) Wenn das Wort „logarithmisch“ Sie dazu bringt, diese Lektion zu beenden und mit dem Lesen aufzuhören, warten Sie einfach ein paar Minuten. Es wird hier keine verrückte Mathematik geben (an anderer Stelle gibt es viele Erklärungen dieser Art), und wir werden jedes Beispiel einzeln herausgreifen. Stellen Sie sich vor, Ihre Aufgabe besteht darin, eine bestimmte Zahl in einem Array von 100 Zahlen zu finden. Genauer gesagt müssen Sie prüfen, ob es vorhanden ist oder nicht. Sobald die erforderliche Nummer gefunden wurde, endet die Suche und Sie zeigen Folgendes in der Konsole an: „Die erforderliche Nummer wurde gefunden! Ihr Index im Array = ....“ Wie würden Sie diese Aufgabe lösen? Hier liegt die Lösung auf der Hand: Sie müssen die Elemente des Arrays einzeln durchlaufen, beginnend mit dem ersten (oder letzten), und prüfen, ob die aktuelle Nummer mit der gesuchten übereinstimmt. Entsprechend, Die Anzahl der Aktionen hängt direkt von der Anzahl der Elemente im Array ab. Wenn wir 100 Zahlen haben, müssen wir möglicherweise 100 Mal zum nächsten Element gehen und 100 Vergleiche durchführen. Wenn es 1000 Zahlen gibt, könnte es 1000 Vergleiche geben. Dies ist offensichtlich lineare Komplexität, d. hO(n) . Und jetzt fügen wir unserem Beispiel eine Verfeinerung hinzu: Das Array, in dem Sie die Zahl finden müssen, wird in aufsteigender Reihenfolge sortiert . Ändert sich dadurch etwas an unserer Aufgabe? Wir könnten immer noch eine Brute-Force-Suche nach der gewünschten Nummer durchführen. Alternativ könnten wir aber auch den bekannten binären Suchalgorithmus verwenden . In der oberen Zeile des Bildes sehen wir ein sortiertes Array. Wir müssen die Nummer 23 darin finden. Anstatt über die Zahlen zu iterieren, teilen wir das Array einfach in zwei Teile und überprüfen die mittlere Zahl im Array. Suchen Sie die Zahl in Zelle 4 und überprüfen Sie sie (zweite Zeile im Bild). Diese Zahl ist 16, und wir suchen nach 23. Die aktuelle Zahl ist geringer als das, was wir suchen. Was bedeutet das? Das bedeutet esAlle vorherigen Zahlen (die vor der Zahl 16 liegen) müssen nicht überprüft werden : Sie sind garantiert kleiner als die gesuchte Zahl, da unser Array sortiert ist! Wir setzen die Suche unter den verbleibenden 5 Elementen fort. Notiz:Wir haben nur einen Vergleich durchgeführt, aber bereits die Hälfte der möglichen Optionen ausgeschlossen. Wir haben nur noch 5 Elemente übrig. Wir wiederholen unseren vorherigen Schritt, indem wir das verbleibende Subarray noch einmal in zwei Hälften teilen und erneut das mittlere Element (die 3. Reihe im Bild) nehmen. Die Zahl beträgt 56 und ist größer als die gesuchte Zahl. Was bedeutet das? Das bedeutet, dass wir drei weitere Möglichkeiten eliminiert haben: die Zahl 56 selbst sowie die beiden Zahlen danach (da sie garantiert größer als 23 sind, da das Array sortiert ist). Wir müssen nur noch zwei Zahlen überprüfen (die letzte Zeile im Bild) – die Zahlen mit den Array-Indizes 5 und 6. Wir überprüfen die erste davon und finden, wonach wir gesucht haben – die Zahl 23! Sein Index ist 5! Schauen wir uns die Ergebnisse unseres Algorithmus an und dann Ich werde seine Komplexität analysieren. Jetzt verstehen Sie übrigens, warum dies als binäre Suche bezeichnet wird: Sie beruht auf der wiederholten Aufteilung der Daten in zwei Hälften. Das Ergebnis ist beeindruckend! Wenn wir eine lineare Suche verwenden würden, um nach der Zahl zu suchen, würden wir bis zu 10 Vergleiche benötigen, aber mit einer binären Suche haben wir die Aufgabe mit nur 3 geschafft! Im schlimmsten Fall gäbe es 4 Vergleiche (wenn im letzten Schritt die gewünschte Zahl die zweite der verbleibenden Möglichkeiten und nicht die erste wäre. Wie sieht es also mit der Komplexität aus? Das ist ein sehr interessanter Punkt :) Der binäre Suchalgorithmus ist viel weniger von der Anzahl der Elemente im Array abhängig als der lineare Suchalgorithmus (d. h. einfache Iteration). Bei 10 Elementen im Array benötigt eine lineare Suche maximal 10 Vergleiche, eine binäre Suche hingegen maximal 4 Vergleiche. Das ist ein Unterschied um den Faktor 2,5. Aber für ein Array mit 1000 Elementen benötigt eine lineare Suche bis zu 1000 Vergleiche, während eine binäre Suche nur 10 erfordern würde ! Der Unterschied beträgt jetzt das 100-fache! Notiz:Die Anzahl der Elemente im Array hat sich um das Hundertfache erhöht (von 10 auf 1000), aber die Anzahl der für eine binäre Suche erforderlichen Vergleiche hat sich nur um den Faktor 2,5 erhöht (von 4 auf 10). Wenn wir 10.000 Elemente erreichen , wird der Unterschied noch beeindruckender: 10.000 Vergleiche für die lineare Suche und insgesamt 14 Vergleiche für die binäre Suche. Und wiederum: Wenn die Anzahl der Elemente um das 1000-fache (von 10 auf 10000) steigt, erhöht sich die Anzahl der Vergleiche nur um den Faktor 3,5 (von 4 auf 14). Die Komplexität des binären Suchalgorithmus ist logarithmisch , oder, wenn wir die Big-O-Notation verwenden, O(log n). Warum heißt es so? Der Logarithmus ist sozusagen das Gegenteil der Potenzierung. Der binäre Logarithmus ist die Potenz, mit der die Zahl 2 erhöht werden muss, um eine Zahl zu erhalten. Wir haben beispielsweise 10.000 Elemente, die wir mit dem binären Suchalgorithmus durchsuchen müssen. Derzeit können Sie anhand der Wertetabelle erkennen, dass hierfür maximal 14 Vergleiche erforderlich sind. Was aber, wenn niemand eine solche Tabelle bereitgestellt hat und Sie die genaue maximale Anzahl an Vergleichen berechnen müssen? Sie müssen nur eine einfache Frage beantworten: Auf welche Potenz muss die Zahl 2 erhöht werden, damit das Ergebnis größer oder gleich der Anzahl der zu prüfenden Elemente ist? Bei 10.000 ist es die 14. Potenz. 2 hoch 13 ist zu klein (8192), aber 2 hoch 14 = 16384, und diese Zahl erfüllt unsere Bedingung (sie ist größer oder gleich der Anzahl der Elemente im Array). Wir haben den Logarithmus gefunden: 14. So viele Vergleiche könnten wir brauchen! :) Algorithmen und algorithmische Komplexität sind ein zu umfassendes Thema, um in eine Lektion zu passen. Aber es ist sehr wichtig, es zu wissen: In vielen Vorstellungsgesprächen geht es um Fragen, die sich mit Algorithmen befassen. Für die Theorie kann ich dir einige Bücher empfehlen. Sie können mit „ Grokking-Algorithmen “ beginnen. Die Beispiele in diesem Buch sind in Python geschrieben, aber das Buch verwendet eine sehr einfache Sprache und Beispiele. Es ist die beste Option für Anfänger und außerdem ist es nicht sehr groß. Zu den ernsteren Lektüren zählen Bücher von Robert Lafore und Robert Sedgewick. Beide sind in Java geschrieben, was Ihnen das Lernen etwas erleichtert. Schließlich sind Sie mit dieser Sprache durchaus vertraut! :) Für Schüler mit guten Mathematikkenntnissen ist das Buch von Thomas Cormen die beste Option . Aber Theorie allein reicht nicht aus! Wissen != Fähigkeit . Sie können das Lösen von Problemen mit Algorithmen auf HackerRank und LeetCode üben . Aufgaben von diesen Websites werden oft auch bei Vorstellungsgesprächen bei Google und Facebook verwendet, sodass Sie sich bestimmt nicht langweilen werden :) Um diesen Unterrichtsstoff zu vertiefen, empfehle ich Ihnen, sich dieses hervorragende Video über die große O-Notation auf YouTube anzusehen. Wir sehen uns in den nächsten Lektionen! :) :)