Komplexität des Algorithmus

Hallo! Der heutige Vortrag wird ein wenig anders sein als der Rest. Der Unterschied besteht darin, dass es nur indirekt mit Java zusammenhängt. Dieses Thema ist jedoch für jeden Programmierer sehr wichtig. Wir werden über Algorithmen sprechen . Was ist ein Algorithmus? Vereinfacht ausgedrückt handelt es sich dabei um eine bestimmte Abfolge von Aktionen, die ausgeführt werden müssen, um das gewünschte Ergebnis zu erzielen . Im Alltag nutzen wir oft Algorithmen. Sie stehen zum Beispiel jeden Morgen vor der Aufgabe, zur Schule oder zur Arbeit zu kommen und gleichzeitig zu sein:

• Angezogen
• Sauber
• Gut genährt

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

1. Wachen Sie mit einem Wecker auf.
2. Duschen, Gesicht waschen.
3. Bereiten Sie Frühstück vor, kochen Sie Kaffee/Tee.
4. Essen.
5. Wenn Sie Ihre Kleidung seit dem Abend nicht mehr gebügelt haben, bügeln Sie sie.
6. Sich anziehen.
7. Das Haus verlassen.

Mit dieser Abfolge von Aktionen können Sie auf jeden Fall das gewünschte Ergebnis erzielen. Beim Programmieren geht es bei unserer Arbeit vor allem darum, ständig Probleme zu lösen. Ein wesentlicher Teil dieser Aufgaben kann mit bereits bekannten Algorithmen erledigt werden. Sie stehen beispielsweise vor einer Aufgabe: Sortieren Sie eine Liste mit 100 Namen in einem Array . Diese Aufgabe ist recht einfach, kann aber auf unterschiedliche Weise gelöst werden. Hier ist eine Lösung: Algorithmus zum alphabetischen Sortieren von Namen:

1. Kaufen oder laden Sie im Internet die Ausgabe „Wörterbuch der russischen Personennamen“ von 1966 herunter.
2. Finden Sie jeden Namen auf unserer Liste in diesem Wörterbuch.
3. Schreiben Sie auf ein Blatt Papier, auf welcher Seite des Wörterbuchs der Name steht.
4. Ordnen Sie die Namen anhand der Notizen auf einem Blatt Papier.

Wird eine solche Abfolge von Aktionen es uns ermöglichen, unser Problem zu lösen? Ja, es wird es völlig zulassen. Wird diese Lösung wirksam sein ? Kaum. Hier kommen wir zu einer weiteren sehr wichtigen Eigenschaft von Algorithmen – ihrer Effizienz . Das Problem kann auf unterschiedliche Weise gelöst werden. Aber sowohl beim Programmieren als auch im Alltag wählen wir die Methode, die am effektivsten ist. Wenn Sie ein Sandwich mit Butter zubereiten möchten, können Sie natürlich zunächst Weizen säen und eine Kuh melken. Dies wird jedoch eine ineffektive Lösung sein – es wird viel Zeit in Anspruch nehmen und viel Geld kosten. Um Ihr einfaches Problem zu lösen, können Sie einfach Brot und Butter kaufen. Und der Algorithmus mit Weizen und Kuh ermöglicht zwar die Lösung des Problems, ist aber zu komplex, um ihn in der Praxis anzuwenden. Um die Komplexität von Algorithmen in der Programmierung einzuschätzen, wurde eine spezielle Notation namens Big-O („big O“) erstellt . Mit Big-O können Sie abschätzen, wie stark die Ausführungszeit eines Algorithmus von den an ihn übergebenen Daten 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. 5000 Kilometer) übertragen. Welcher Algorithmus ist der effizienteste? Es hängt von den Daten ab, mit denen er arbeiten muss. Wir haben beispielsweise eine Audiodatei mit einer Größe von 10 Megabyte. In diesem Fall wäre der effizienteste Algorithmus die Übertragung der Datei über das Internet. Es dauert nur ein paar Minuten! Lassen Sie uns unseren Algorithmus noch einmal formulieren: „Wenn Sie Informationen in Form von Dateien über eine Entfernung von 5000 Kilometern übertragen müssen, müssen Sie die Datenübertragung über das Internet nutzen.“ Großartig. Jetzt analysieren wir es. Löst es unser Problem? Im Allgemeinen ja, es löst das Problem vollständig. Aber was können Sie über seine Komplexität sagen? Hmm, jetzt wird es interessant. Tatsache ist, dass unser Algorithmus stark von den eingehenden Daten abhängt, nämlich von der Größe der Dateien. Jetzt haben wir 10 Megabyte und alles ist in Ordnung. Was ist, wenn wir 500 Megabyte übertragen müssen? 20 Gigabyte? 500 Terabyte? 30 Petabyte? Wird unser Algorithmus nicht mehr funktionieren? Nein, alle diese Datenmengen können weiterhin übertragen werden. Wird die Fertigstellung länger dauern? Ja, es wird! Jetzt kennen wir ein wichtiges Merkmal unseres Algorithmus: Je größer die zu übertragenden Daten sind, desto länger dauert die Fertigstellung des Algorithmus . Aber wir würden gerne genauer verstehen, wie dieser Zusammenhang aussieht (zwischen der Größe der Daten und der Zeit, die für die Übertragung benötigt wird). In unserem Fall ist die Komplexität des Algorithmus linear. „Linear“ bedeutet, dass mit zunehmender Datenmenge die Zeit für deren Übertragung ungefähr proportional zunimmt. Wenn doppelt so viele Daten vorhanden sind, dauert die Übertragung doppelt so lange. Wenn zehnmal mehr Daten vorhanden sind, erhöht sich die Übertragungszeit um das Zehnfache. Unter Verwendung der Big-O-Notation wird die Komplexität unseres Algorithmus als O(N) definiert . Diese Notation sollte man sich am besten zum späteren Nachschlagen merken; sie wird immer für Algorithmen mit linearer Komplexität verwendet. Bitte beachten Sie: Wir sprechen hier überhaupt nicht über verschiedene „variable“ Dinge: Internetgeschwindigkeit, die Leistung unseres Computers und so weiter. Bei der Beurteilung der Komplexität eines Algorithmus macht das einfach keinen Sinn – wir haben sowieso keine Kontrolle darüber. Big-O bewertet den Algorithmus selbst, unabhängig von der „Umgebung“, in der er arbeiten muss. Fahren wir mit unserem Beispiel fort. Nehmen wir an, es stellt sich irgendwann heraus, dass die Größe der zu übertragenden Dateien 800 Terabyte beträgt. Wenn wir sie über das Internet übertragen, ist das Problem natürlich gelöst. Es gibt nur ein Problem: Die Übertragung über eine moderne Standardverbindung (mit 100 Megabit pro Sekunde), die die meisten von uns zu Hause nutzen, dauert etwa 708 Tage. Fast 2 Jahren! :O Unser Algorithmus ist hier also eindeutig nicht geeignet. Wir brauchen eine andere Lösung! Plötzlich kommt uns der IT-Riese Amazon zu Hilfe! Mit dem Service Amazon Snowmobile können Sie große Datenmengen in mobile Speichereinheiten laden und 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 Kilometern übertragen müssen und der Vorgang bei der Übertragung über das Internet mehr als 14 Tage dauert, müssen Sie den LKW-Transport von Amazon nutzen.“ Die Zahl von 14 Tagen wurde hier zufällig gewählt: Nehmen wir an, das ist der maximale Zeitraum, den wir uns leisten können. Lassen Sie uns unseren Algorithmus analysieren. Wie sieht es mit der Geschwindigkeit aus? Selbst wenn der Lkw nur 50 km/h schnell fährt, schafft er in nur 100 Stunden 5.000 Kilometer. Das sind etwas mehr als vier Tage! Dies ist viel besser als die Möglichkeit der Internetübertragung. Wie sieht es mit der Komplexität dieses Algorithmus aus? Wird es auch linear sein, O(N)? Nein es wird nicht. Denn dem LKW ist es egal, wie viel Sie beladen – er fährt immer noch ungefähr mit der gleichen Geschwindigkeit und kommt pünktlich an. Unabhängig davon, ob wir 800 Terabyte oder zehnmal mehr Daten haben, wird der LKW immer noch in 5 Tagen dort ankommen. Mit anderen Worten: Der Algorithmus zur Übermittlung von Daten per LKW weist eine konstante Komplexität auf . „Konstant“ bedeutet, dass es nicht von den an den Algorithmus übergebenen Daten abhängt. Legen Sie ein 1-GB-Flash-Laufwerk in den LKW und es kommt in 5 Tagen an. Legen Sie dort Festplatten mit 800 Terabyte an Daten ein und sie werden in 5 Tagen eintreffen. Bei Verwendung von Big-O wird konstante Komplexität als O(1) bezeichnet . Seitdem wir O(N) und kennengelernt habenO(1) , schauen wir uns nun weitere „Programmierer“-Beispiele an :) Nehmen wir an, Sie erhalten ein Array mit 100 Zahlen und die Aufgabe besteht darin, jede davon auf der Konsole auszugeben. Sie schreiben eine reguläre Schleife for, die diese Aufgabe ausführt

int[] numbers = new int[100];
// ..заполняем массив числами

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

Wie komplex ist der geschriebene Algorithmus? Linear, O(N). Die Anzahl der Aktionen, die das Programm ausführen muss, hängt davon ab, wie viele Zahlen genau an das Programm übergeben wurden. Wenn das Array 100 Zahlen enthält, gibt es 100 Aktionen (Ausgaben auf dem Bildschirm). Wenn das Array 10.000 Zahlen enthält, müssen 10.000 Aktionen ausgeführt werden. Kann unser Algorithmus verbessert werden? Nein. In jedem Fall müssen wir N Durchgänge durch das Array durchführen und N Ausgaben an die Konsole durchführen. Schauen wir uns ein anderes Beispiel an.

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 leeres LinkedList, in das wir mehrere Zahlen einfügen. Wir müssen die Komplexität des Algorithmus zum Einfügen einer einzelnen Zahl in LinkedListunser Beispiel abschätzen und wie sie von der Anzahl der Elemente in der Liste abhängt. Die Antwort ist O(1) – konstante Komplexität . Warum? Bitte beachten Sie: Jedes Mal fügen wir am Anfang der Liste eine Nummer ein. Darüber hinaus werden beim Einfügen von Zahlen in LinkedListElemente, wie Sie sich erinnern, diese nirgendwo verschoben – Links werden neu definiert (wenn Sie plötzlich vergessen haben, wie LinkedList funktioniert, schauen Sie sich eine unserer alten Vorlesungen an ). Wenn nun die erste Zahl in unserer Liste die Zahl ist хund wir die Zahl y am Anfang der Liste einfügen, brauchen wir nur noch:

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

Für diese Neudefinition der Referenz spielt es für uns keine Rolle, wie viele Zahlen es jetzt gibtLinkedList – mindestens eine, mindestens eine Milliarde. Die Komplexität des Algorithmus wird konstant sein – O(1).

Logarithmische Komplexität

Keine Panik! :) Wenn das Wort „logarithmisch“ Sie dazu bringt, die Vorlesung zu beenden und nicht weiterzulesen, warten Sie ein paar Minuten. Hier wird es keine mathematischen Schwierigkeiten geben (an anderen Stellen gibt es viele solcher Erklärungen) und wir werden alle Beispiele „an den Fingern“ analysieren. Stellen Sie sich vor, Ihre Aufgabe besteht darin, eine bestimmte Zahl in einem Array von 100 Zahlen zu finden. Genauer gesagt: Überprüfen Sie, ob es überhaupt vorhanden ist. Sobald die gesuchte Nummer gefunden wurde, muss die Suche abgebrochen werden und in der Konsole sollte der Eintrag „Die gesuchte Nummer wurde gefunden!“ angezeigt werden. Sein Index im Array = ....“ Wie würden Sie ein solches Problem lösen? Hier liegt die Lösung auf der Hand: Sie müssen die Array-Elemente einzeln durchlaufen, beginnend mit dem ersten (oder letzten), und prüfen, ob die aktuelle Nummer mit der gewünschten übereinstimmt. Dementsprechend hängt die Anzahl der Aktionen direkt von der Anzahl der Elemente im Array ab. Wenn wir 100 Zahlen haben, müssen wir 100 Mal zum nächsten Element gehen und die Zahl 100 Mal auf Übereinstimmung prüfen. Wenn es 1000 Zahlen gibt, dann gibt es 1000 Prüfschritte. Dies ist offensichtlich lineare Komplexität, O(N) . Nun fügen wir unserem Beispiel eine Klarstellung hinzu: Das Array, in dem Sie eine Zahl finden müssen, wird in aufsteigender Reihenfolge sortiert . Ändert sich dadurch etwas für unsere Aufgabe? Wir können immer noch mit roher Gewalt nach der gewünschten Nummer suchen. Aber wir können stattdessen den bekannten binären Suchalgorithmus verwenden . In der oberen Zeile des Bildes sehen wir ein sortiertes Array. Darin müssen wir die Zahl 23 finden. Anstatt über die Zahlen zu iterieren, teilen wir das Array einfach in zwei Teile und überprüfen die durchschnittliche Zahl im Array. Wir finden die Nummer, die sich in Zelle 4 befindet, und überprüfen sie (zweite Zeile im Bild). Diese Zahl ist 16 und wir suchen 23. Die aktuelle Zahl ist niedriger. Was bedeutet das? Dass alle vorherigen Zahlen (die bis zur Zahl 16 liegen) nicht überprüft werden müssen : Sie werden definitiv kleiner sein als die gesuchte, weil unser Array sortiert ist! Lassen Sie uns die Suche unter den verbleibenden 5 Elementen fortsetzen. Passt auf:Wir haben nur eine Prüfung durchgeführt, aber bereits die Hälfte der möglichen Optionen ausgeschlossen. Wir haben nur noch 5 Elemente übrig. Wir werden unseren Schritt wiederholen – das verbleibende Array erneut durch 2 teilen und erneut das mittlere Element nehmen (Zeile 3 in der Abbildung). Diese Zahl beträgt 56 und ist größer als die gesuchte Zahl. Was bedeutet das? Dass wir drei weitere Optionen verwerfen – die Zahl 56 selbst und zwei Zahlen danach (sie sind definitiv größer als 23, da das Array sortiert ist). Wir müssen nur noch 2 Zahlen überprüfen (die letzte Zeile in der Abbildung) – Zahlen mit den Array-Indizes 5 und 6. Wir überprüfen die erste davon und das ist es, wonach wir gesucht haben – die Zahl 23! Sein Index = 5! Schauen wir uns die Ergebnisse unseres Algorithmus an und dann werden wir seine Komplexität verstehen. (Übrigens verstehen Sie jetzt, warum es Binär genannt wird: Sein Wesen besteht darin, Daten ständig durch 2 zu dividieren.) Das Ergebnis ist beeindruckend! Wenn wir mit der linearen Suche nach der gewünschten Zahl suchen würden, würden wir 10 Prüfungen benötigen, aber mit der binären Suche haben wir es in 3 geschafft! Im schlimmsten Fall wären es 4 davon, wenn sich im letzten Schritt herausstellen würde, dass die von uns benötigte Zahl die zweite und nicht die erste ist. Wie sieht es mit seiner Komplexität aus? Das ist ein sehr interessanter Punkt :) Der binäre Suchalgorithmus hängt viel weniger von der Anzahl der Elemente im Array ab als der lineare Suchalgorithmus (d. h. einfache Aufzählung). Bei 10 Elementen im Array sind für die lineare Suche maximal 10 Prüfungen und für die binäre Suche maximal 4 Prüfungen erforderlich. Der Unterschied beträgt das 2,5-fache. Aber für ein Array mit 1000 Elementen benötigt die lineare Suche 1000 Prüfungen und die binäre Suche nur 10 ! Der Unterschied beträgt bereits das 100-fache! Passt auf:Die Anzahl der Elemente im Array hat sich um das Hundertfache erhöht (von 10 auf 1000), und die Anzahl der erforderlichen Prüfungen für die binäre Suche hat sich nur um das 2,5-fache erhöht – von 4 auf 10. Wenn wir 10.000 Elemente erreichen , ist der Unterschied noch beeindruckender: 10.000 Prüfungen für die lineare Suche und insgesamt 14 Prüfungen für die binäre Suche. Und noch einmal: Die Anzahl der Elemente erhöhte sich um das 1000-fache (von 10 auf 10000), die Anzahl der Prüfungen jedoch nur um das 3,5-fache (von 4 auf 14). Die Komplexität des binären Suchalgorithmus ist logarithmisch oder in der Big-O-Notation O(log n) . Warum heißt es so? Ein Logarithmus ist die Umkehrung der Potenzierung. Der binäre Logarithmus wird verwendet, um die Potenz von 2 zu berechnen. Beispielsweise haben wir 10.000 Elemente, die wir mithilfe einer binären Suche durchgehen müssen. Jetzt haben Sie ein Bild vor Augen und wissen, dass dafür maximal 14 Prüfungen erforderlich sind. Was aber, wenn Sie kein Bild vor Augen haben und die Anzahl der notwendigen Schecks genau abzählen müssen? Es reicht aus, eine einfache Frage zu beantworten: Mit welcher Potenz sollte die Zahl 2 erhöht werden, damit das erhaltene Ergebnis >= der Anzahl der überprüften Elemente ist? Für 10000 ist es die 14. Potenz. 2 hoch 13 ist zu klein (8192) Aber 2 hoch 14 = 16384 , diese Zahl erfüllt unsere Bedingung (sie ist >= die Anzahl der Elemente im Array). Wir haben den Logarithmus gefunden – 14. So viele Schecks brauchen wir! :) Algorithmen und ihre Komplexität sind ein zu umfangreiches Thema, um es in einer Vorlesung zu behandeln. Aber es ist sehr wichtig, es zu wissen: In vielen Interviews werden Sie auf algorithmische Probleme stoßen. Zur Theorie kann ich dir mehrere Bücher empfehlen. Ein guter Ausgangspunkt ist „ Grocking Algorithms “: Obwohl die Beispiele im Buch in Python geschrieben sind, sind die Sprache und die Beispiele des Buches sehr einfach. Die beste Option für Anfänger, außerdem hat es ein geringes Volumen. Ernsthaftere Lektüre: Bücher von Robert Laforet und Robert Sedgwick . Beide sind in Java geschrieben, was Ihnen das Lernen etwas erleichtert. Schließlich sind Sie mit dieser Sprache durchaus vertraut! :) Für Studenten mit einem guten mathematischen Hintergrund wäre das Buch von Thomas Corman die beste Option . Aber Sie werden sich nicht mit der bloßen Theorie zufrieden geben! „Wissen“ != „können“ Sie können das Lösen von Algorithmusproblemen auf HackerRank und Leetcode üben . Probleme von dort werden oft auch bei Interviews bei Google und Facebook verwendet, sodass Sie sich bestimmt nicht langweilen werden :) Um den Vorlesungsstoff zu vertiefen, empfehle ich Ihnen, sich ein hervorragendes Video über Big-O auf YouTube anzusehen. Wir sehen uns bei den nächsten Vorträgen! :) :)