WEB LEXIKON: Ein Blick zurück
Hauptseite | Aktueller Wikipedia-Artikel

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 jedesmal, 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:




     
Das Web Lexikon "Ein Blick zurück" bietet die Moeglichkeit auf einfache Art und Weise in den "alten" Wikipedia-Beiträgen zu blättern. Das Lexikon spiegelt den Stand der freien Wikipedia-Enzyklopädie vom August 2004 wider. Sie finden hier in rund 120.000 Artikel aus dieser Zeit Informationen, Erklärungen, Definitionen, Empfehlungen, Beschreibungen, Auskünfte und Bilder. Ebenso kommen Begriffserklärung, Zusammenfassung, Theorie, Information, Beschreibung, Erklärung, Definition und Geschichte nicht zu kurz. Ein Lexikon das Auskunft, Bericht, Hinweis, Bedeutung, Bild, Aufklärung, Darstellung und Schilderung zu unterschiedlichsten Themen kompakt auf einer Seite bietet.
Impressum ^ nach oben ^