Grundlagen der Algorithmen
Ein Algorithmus ist eine klare, endliche Menge von Schritten zur Lösung eines bestimmten Problems.
Das Verständnis der grundlegenden Konzepte von Algorithmen und Methoden zur Effizienzanalyse ist eine wichtige Voraussetzung für das Erlernen von Datenstrukturen und Algorithmen.
Definition und Eigenschaften von Algorithmen
In der Informatik ist ein Algorithmus eine endliche Folge von Anweisungen, von denen jede eine oder mehrere Operationen darstellt.
Ein qualifizierter Algorithmus muss die folgenden fünf grundlegenden Eigenschaften besitzen:
| Eigenschaft | Bedeutung | Gegenbeispiel |
|---|---|---|
| Eingabe | Es gibt null oder mehr externe Eingaben | Keine Eingabe ist ebenfalls gültig, wie das Generieren von Zufallszahlen |
| Ausgabe | Erzeugt mindestens ein Ergebnis | Ein „Algorithmus“ ohne Ausgabe ist bedeutungslos |
| Bestimmtheit | Die Bedeutung jedes Schrittes muss klar und eindeutig sein | Vage Beschreibungen wie „angemessen erhöhen“ sind inakzeptabel |
| Endlichkeit | Muss nach endlich vielen Schritten terminieren; darf nicht unbegrenzt schleifen | Ein Betriebssystem selbst ist kein Algorithmus, da es theoretisch endlos läuft |
| Ausführbarkeit | Jeder Schritt kann mit grundlegenden Operationen umgesetzt werden | „Division durch null“ ist nicht ausführbar, und „Sortieren in einem Schritt“ ist ebenfalls nicht ausführbar |
Die „Endlichkeit“ eines Algorithmus steht nicht im Widerspruch zur „Endlosschleife“ eines Programms. Ein Programm kann aufgrund eines Fehlers in eine Endlosschleife geraten, aber ein Algorithmus selbst muss nach endlich vielen Schritten beendet sein. Der Unterschied ist: Ein Algorithmus ist ein Konzept auf der Ebene der „Entwurfsabsicht“, während ein Programm ein Konzept auf der Ebene der „tatsächlichen Ausführung“ ist.
Darstellungsmethoden für Algorithmen
Beim Entwerfen und Kommunizieren von Algorithmen werden häufig zwei Darstellungsmethoden verwendet.
Pseudocode
Pseudocode verwendet Text, der der natürlichen Sprache nahe kommt, aber ein bestimmtes strukturiertes Format hat, um die Logik von Algorithmen zu beschreiben.
Er hängt nicht von der Syntax einer bestimmten Programmiersprache ab, wodurch sich Ideen schnell ausdrücken lassen.
Zum Beispiel Pseudocode zum Finden des Maximalwerts in einer Menge von Zahlen:
算法：FindMax 输入：数组 A，长度 n 输出：A 中的最大值 1. max = A[0] 2. for i = 1 to n-1: 3. if A[i] > max: 4. max = A[i] 5. return max
Flussdiagramm
Ein Flussdiagramm stellt den Ausführungsprozess eines Algorithmus visuell durch Grafiken dar.
Die obige Abbildung zeigt den vollständigen Ausführungsprozess des FindMax-Algorithmus: Ausgehend vom Eingabearray wird das aktuelle Maximum initialisiert, dann wird jedes Element der Reihe nach verglichen, das Maximum aktualisiert, wenn ein größerer Wert gefunden wird, und nach Abschluss des Durchlaufs wird das Ergebnis ausgegeben.
Symbolkonventionen in Flussdiagrammen:
| Symbolform | Bedeutung |
|---|---|
| Abgerundetes Rechteck (oder Ellipse) | Start / Ende |
| Rechteck | Verarbeitungsschritt |
| Raute | Entscheidung / Verzweigung |
| Parallelogramm | Eingabe / Ausgabe |
| Pfeil | Flussrichtung |
Effizienzanalyse von Algorithmen
Nachdem ein Algorithmus entworfen wurde, muss auch seine Effizienz bewertet werden. Diese wird hauptsächlich anhand von zwei Dimensionen gemessen.
Zeitkomplexität
Die Zeitkomplexität beschreibt den Wachstumstrend der Anzahl der vom Algorithmus benötigten Basisoperationen, wenn die Eingabegröße n zunimmt.
Beachten Sie, dass wir uns für den „Wachstumstrend“ und nicht für die „genaue Anzahl der Ausführungen“ interessieren. Denn bei Eingaben in großem Maßstab sind Unterschiede um konstante Vielfache weit weniger wichtig als Unterschiede in den Wachstumstrends.
Speicherkomplexität
Speicherkomplexität beschreibt den Wachstumstrend des zusätzlichen Speicherplatzes, der während der Ausführung eines Algorithmus benötigt wird, wenn die Eingabegröße n zunimmt.
Die Betonung auf "zusätzlichem" Speicherplatz bedeutet hier, wie viel Hilfsspeicher der Algorithmus zusätzlich zu dem Speicher benötigt, der zum Speichern der Eingabedaten selbst verwendet wird.
Zeit und Speicher sind oft ein Paar von Abwägungen – Speicher gegen Zeit einzutauschen oder Zeit gegen Speicher einzutauschen, ist eine übliche Kompromissstrategie im Algorithmusentwurf. Zum Beispiel: Eine Hash-Tabelle verwendet zusätzlichen Speicherplatz, um eine Nachschlagezeit von O(1) zu erreichen; wohingegen In-Place-Sortieralgorithmen etwas mehr Berechnungsschritte verwenden, um zusätzlichen Speicherverbrauch zu vermeiden.
Big-O-Notation
Big-O-NotationSie ist das am häufigsten verwendete mathematische Werkzeug zur Messung der Zeitkomplexität und der Speicherkomplexität.
Sie beschreibt die obere Schranke des Wachstumstrends der Laufzeit oder des Speicherverbrauchs, wenn die Eingabegröße n zunimmt, im Worst-Case-Szenario für einen Algorithmus.
Definition: Wenn positive Konstanten c und n0 existieren, sodass für alle n ≥ n0 gilt: T(n) ≤ c × f(n), dann wird es notiert alsT(n) = O(f(n))。
Intuitives Verständnis: Die Big-O-Notation ignoriert konstante Faktoren und Terme niedrigerer Ordnung und konzentriert sich nur auf den am schnellsten wachsenden Term.
Zum Beispiel: Wenn ein Algorithmus 3n² + 100n + 500 Operationen benötigt, dominiert bei ausreichend großem n der Term n² das Wachstum, daher sagen wir, er ist O(n²).
Häufige Komplexitätsstufen
Die obige Abbildung zeigt anschaulich, wie sich jede Komplexitätsstufe ändert, wenn die Eingabegröße n wächst.
| Notation | Name | n=10 | n=1000 | Typische Algorithmen |
|---|---|---|---|---|
| O(1) | Konstante Ordnung | 1 | 1 | Array-Zugriff per Index, Hash-Tabellen-Suche |
| O(log n) | Logarithmische Ordnung | ~3 | ~10 | Binäre Suche, Operationen auf balancierten BSTs |
| O(n) | Lineare Ordnung | 10 | 1000 | Lineare Suche, Durchlaufen eines Arrays |
| O(n log n) | Linearithmische Ordnung | ~30 | ~10000 | Mergesort, Quicksort (durchschnittlich) |
| O(n²) | Quadratische Ordnung | 100 | 1000000 | Bubblesort, Selectionsort |
| O(2ⁿ) | Exponentielle Ordnung | 1024 | Astronomische Zahl | Brute-Force-Lösen von Teilmengenproblemen |
Aus der Tabelle ist ersichtlich, dass bei n=1000 O(1) weiterhin nur 1 Operation erfordert, O(n) 1000 Operationen erfordert und O(n²) 1 Million Operationen erfordert.
In Szenarien mit großen Datenmengen kann die Wahl eines Algorithmus mit angemessener Komplexität zu Leistungsunterschieden in Größenordnungen führen.
In der tatsächlichen Programmierung sollte man versuchen, sicherzustellen, dass die Komplexität von Kernalgorithmen O(n log n) nicht überschreitet. Wenn die Komplexität O(n²) oder höher erreicht, muss besonders darauf geachtet werden, ob die Eingabegröße kontrollierbar ist und ob es bessere Alternativen gibt.
Beispiele zur Berechnung der Zeitkomplexität
Unten folgt ein einfaches C-Code-Schnipsel und seine Zeitkomplexitätsanalyse:
Beispiel
/* Funktion: Berechnung der Summe der Array-Elemente
Zeitkomplexität: O(n)
n ist die Array-Länge, die Schleife läuft n-mal, und jede Iteration führt eine konstante Anzahl von Operationen aus */
int sumArray(int arr[], int n) {
int total = 0; /* O(1) — Zuweisungsoperation, einmal ausgeführt */
for (int i = 0; i < n; i++) { /* Schleifenkörper */
total += arr[i]; /* O(1) — Addition und Zuweisung, n-mal ausgeführt */
}
return total; /* O(1) — Rückgabeoperation, einmal ausgeführt */
}
/* Gesamte Zeitkomplexität: O(1 + n + 1) = O(n)
Konstante Terme niedrigerer Ordnung werden ignoriert */
int main() {
int nums[] = {5, 10, 15, 20, 25};
int size = sizeof(nums) / sizeof(nums[0]);
int result = sumArray(nums, size);
printf("Summe der Array-Elemente: %d\n", result); /* Ausgabe: Summe der Array-Elemente: 75 */
return 0;
}
Betrachten Sie nun ein weiteres Beispiel mit verschachtelten Schleifen:
Beispiel
/* Funktion: eine n×n-Multiplikationstabelle ausgeben
Zeitkomplexität: O(n²)
Die äußere Schleife wird n-mal ausgeführt, die innere Schleife wird n-mal ausgeführt, insgesamt n×n-mal */
void printMulTable(int n) {
for (int i = 1; i <= n; i++) { /* Äußere Schleife O(n) */
for (int j = 1; j <= n; j++) { /* Innere Schleife O(n), insgesamt n² Iterationen nach der Verschachtelung */
printf("%d\t", i * j); /* O(1)-Operation */
}
printf("\n");
}
}
/* Gesamtzeitkomplexität: O(n × n) = O(n²) */
int main() {
printMulTable(5); /* Eine 5×5-Multiplikationstabelle ausgeben */
return 0;
}
Beispiele zur Berechnung der Speicherkomplexität
Die Speicherkomplexität betrachtet den zusätzlichen Speicherplatz, der während der Ausführung eines Algorithmus zugewiesen wird.
Beispiel
#include <stdlib.h> /* Header-Datei für malloc/free */
/* Funktion: ein neues Array erstellen, das die Quadrate des ursprünglichen Arrays speichert
Speicherkomplexität: O(n) — reserviert ein neues Array der Länge n */
int* squareArray(int arr[], int n) {
int* result = (int*)malloc(n * sizeof(int)); /* Zusätzlichen Speicher für n int-Werte reservieren */
if (result == NULL) {
return NULL; /* NULL zurückgeben, wenn malloc fehlschlägt */
}
for (int i = 0; i < n; i++) {
result[i] = arr[i] * arr[i];
}
return result;
}
/* Speicherkomplexität O(n):
- Das Eingabearray arr wird nicht mitgezählt (es ist Teil der Eingabe selbst)
- Das Ergebnisarray reserviert zusätzlich n int-Werte, was zusätzlichen Speicherplatz darstellt
- Variable i verwendet konstanten Speicher O(1), wird von O(n) dominiert */
int main() {
int nums[] = {1, 2, 3, 4, 5};
int n = 5;
int* squared = squareArray(nums, n);
if (squared != NULL) {
for (int i = 0; i < n; i++) {
printf("%d ", squared[i]); /* Ausgabe: 1 4 9 16 25 */
}
printf("\n");
free(squared); /* Den dynamisch zugewiesenen Speicher manuell freigeben */
}
return 0;
}
Weitere ErweiterungenHäufige Anfängermissverständnisse: Zeitkomplexität und Speicherkomplexität analysieren "Wachstumstrends" statt exakter Werte. Konstante Koeffizienten, Terme niedrigerer Ordnung und Unterschiede zwischen Programmiersprachen werden von der Big-O-Notation allesamt ignoriert. Daher sind O(2n) und O(n) äquivalent – sie repräsentieren beide lineares Wachstum.