imported>Invisigoth67: typo

2024-09-06T07:57:43Z

typo

Neue Seite

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 [[polynomieller Algorithmus|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:

# Setze die erste Zahl der Liste als (vorläufiges) Maximum.
# 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.''
# 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 [[Anweisung (Programmierung)|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-Symbol]]e und schreibt hierfür kurz O(''n'').

[[Kategorie:Algorithmus]]
[[Kategorie:Komplexitätstheorie]]

Linearer Algorithmus - Versionsgeschichte

imported>Invisigoth67: typo