Algorithmus: Unterschied zwischen den Versionen
Thomas (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Thomas (Diskussion | Beiträge) |
||
| (5 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
Ein '''Algorithmus''' ist in der Informatik ein genau beschriebenes Verfahren zur Lösung eines gegebenen Problems. Ein '''Programm''' stellt die Übersetzung eines Algorithmus in eine vom Computer begreifbare und ausführbare Folge von Befehlen dar, an dessen Ende die Lösung eines Problems ausgegeben wird. | Ein '''Algorithmus''' ist in der Informatik ein genau beschriebenes Verfahren zur Lösung eines gegebenen Problems. Ein '''Programm''' stellt die Übersetzung eines Algorithmus in eine vom Computer begreifbare und ausführbare Folge von Befehlen dar, an dessen Ende die Lösung eines Problems ausgegeben wird. | ||
| Zeile 62: | Zeile 60: | ||
Die Anzahl der Schritte, die ein Algorithmus benötigt, wird als die [[Laufzeit]] des Algorithmus bezeichnet. Der Begriff Schritt bezieht sich auf das zugrunde gelegte Maschinenmodell. Die Maschine (der Computer) muss in der Lage sein, einen einzelnen Schritt in konstanter Zeit auszuführen. Die Laufzeit hängt im allgemeinen von der Eingabe ab, insbesondere von der Länge der Eingabe, die auch als Problemgröße bezeichnet wird. | Die Anzahl der Schritte, die ein Algorithmus benötigt, wird als die [[Laufzeit]] des Algorithmus bezeichnet. Der Begriff Schritt bezieht sich auf das zugrunde gelegte Maschinenmodell. Die Maschine (der Computer) muss in der Lage sein, einen einzelnen Schritt in konstanter Zeit auszuführen. Die Laufzeit hängt im allgemeinen von der Eingabe ab, insbesondere von der Länge der Eingabe, die auch als Problemgröße bezeichnet wird. | ||
Beispiel: Die [[Laufzeit]] eines [[Sortieralgorithmus]] ist umso größer, je mehr Elemente zu sortieren sind. Soll eine Liste von fünf Zahlen sortiert werden, so ist die Problemgröße n=5. | Beispiel: Die [[Laufzeitanalyse|Laufzeit]] eines [[Sortieren|Sortieralgorithmus]] ist umso größer, je mehr Elemente zu sortieren sind. Soll eine Liste von fünf Zahlen sortiert werden, so ist die Problemgröße n=5. | ||
Bei einer vorsortierten Eingabefolge benötigt der Algorithmus möglicherweise weniger Schritte als bei einer unsortierten Eingabefolge gleicher Länge. Eine vorsortierte Liste stellt das Best Case Szenario dar. Also den günstigsten Fall für das gegebene Problem (hier das Sortieren von Zahlen). Eine sortierte Liste in umgekehrter Reihenfolge stellt das Worst Case Szenario dar. Hier ist der Aufwand am größten die Liste umzusortieren. | Bei einer vorsortierten Eingabefolge benötigt der Algorithmus möglicherweise weniger Schritte als bei einer unsortierten Eingabefolge gleicher Länge. Eine vorsortierte Liste stellt das Best Case Szenario dar. Also den günstigsten Fall für das gegebene Problem (hier das Sortieren von Zahlen). Eine sortierte Liste in umgekehrter Reihenfolge stellt das Worst Case Szenario dar. Hier ist der Aufwand am größten die Liste umzusortieren. | ||
Um den Algorithmus unabhängig von der konkreten Eingabe bewerten zu können, betrachtet man die Zeitkomplexität in der so genannten Laufzeitanalyse. | Um den Algorithmus unabhängig von der konkreten Eingabe bewerten zu können, betrachtet man die Zeitkomplexität in der so genannten [[Laufzeitanalyse]]. | ||
== Beispiel == | == Beispiel == | ||
| Zeile 94: | Zeile 92: | ||
} | } | ||
</syntaxhighlight> | </syntaxhighlight> | ||
[[Kategorie:Programmierung]] | |||
[[Kategorie:AHR_I_Informatik_LK]] | |||
[[Kategorie:FI_I_SDM]] | |||
[[Kategorie:FI_I_TP1]] | |||