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
- Wachen Sie mit einem Wecker auf.
- Duschen Sie und waschen Sie sich.
- Bereiten Sie Frühstück und Kaffee oder Tee zu.
- Essen.
- Wenn Sie Ihre Kleidung am Vorabend nicht gebügelt haben, dann bügeln Sie sie.
- Sich anziehen.
- Das Haus verlassen.
- Kaufen oder laden Sie die Ausgabe von Webster's Third New International Dictionary aus dem Jahr 1961 herunter.
- Finden Sie jeden Namen aus unserer Liste in diesem Wörterbuch.
- Schreiben Sie auf ein Blatt Papier die Seite des Wörterbuchs, auf der sich der Name befindet.
- Verwenden Sie die Zettel, um die Namen zu sortieren.
for
Schleife, 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 LinkedList
unser 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 LinkedList
die 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 x
und 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).