Linearer Algorithmus

Ein linearer Algorithmus ist ein Algorithmus, dessen Laufzeit linear in der Größe der Eingabe ist. Dies bedeutet, dass der Algorithmus für eine doppelt so große Eingabe in etwa doppelt so lange braucht. Man sagt auch: „Der Algorithmus ist in O(n)“.

Lineare Algorithmen werden in der Regel als sehr schnelle Algorithmen angesehen. Sie gehören der Klasse der polynomiellen Algorithmen an.

Beispiel

Für die Aufgabe, die größte Zahl aus einer Liste mit n Einträgen zu finden, gibt es einen linearen Algorithmus:

1. Setze die erste Zahl der Liste als (vorläufiges) Maximum.
2. Gehe jetzt die restlichen Zahlen der Reihe nach durch und überprüfe jedes Mal, ob …

   … diese Zahl größer ist, als das bisherige Maximum.

   Wenn ja, dann ersetze das (vorläufige) Maximum durch diese Zahl.

3. Der Algorithmus ist fertig, wenn die letzte Zahl überprüft wurde.

Die Größe der Eingabe ist hier die Anzahl der Zahlen in der Liste. Um die Laufzeit des Algorithmus zu berechnen betrachtet man die Anweisungen der Reihe nach:

• Die erste Anweisung dauert eine Zeiteinheit.
• Danach kommt eine Schleife, die n-1 mal durchlaufen wird. In der Schleife werden ein oder zwei Anweisungen ausgeführt, damit bekommt man eine Laufzeit l zwischen n-1 und 2·(n-1) für die Schleife.
• Nimmt man alles zusammen, so ist die Laufzeit c·(n), mit einer Konstanten c, die zwischen 1 und 2 liegt und die von der konkreten Eingabe abhängt. Um solche Abhängigkeiten zu vermeiden benutzt man die sogenannten Landau-Symbole, und schreibt hierfür kurz O(n).