Linearer Algorithmus - LinkFang.de





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).

Kategorien: Algorithmus | Komplexitätstheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Linearer Algorithmus (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.