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.
1. Setze die erste Zahl der Liste als (vorläufiges) Maximum.
2. Gehe jetzt die restlichen Zahlen der Reihe nach durch und überprüfe jedesmal, ob
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:
Beispiel
Für die Aufgabe, die größte Zahl aus einer Liste mit n Einträgen zu finden, gibt es einen linearen Algorithmus:
3. Der Algorithmus ist fertig, wenn die letzte Zahl überprüft wurde.