Laufzeitanalyse: Unterschied zwischen den Versionen
Thomas (Diskussion | Beiträge) Die Seite wurde neu angelegt: „== Einführung == Die Laufzeitanalyse betrachtet die Zeitkomplexität eines Algorithmus. Da die Zeit zur Ausführung eines Algorithmuses von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine Betrachtung die Anzahl der Befehle analysiert, die ein Algorithmus zur Lösung eines gegebenen Problems benötigt. Die Lösung eines Problems mit Hilfe eines gegebenen Algorithmus ist abhängig von der Eingabe. Die Eingabe…“ |
Thomas (Diskussion | Beiträge) |
||
| Zeile 1: | Zeile 1: | ||
== Einführung == | == Einführung == | ||
Die Laufzeitanalyse betrachtet die Zeitkomplexität eines [[Algorithmus]]. Da die Zeit zur Ausführung eines Algorithmuses von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine Betrachtung die Anzahl der [[Anweisung|Befehle]] analysiert, die ein Algorithmus zur Lösung eines gegebenen Problems benötigt. Die Lösung eines Problems mit Hilfe eines gegebenen Algorithmus ist abhängig von der Eingabe. Die Eingabe wird auch als Problemgröße bezeichnet. | Die Laufzeitanalyse betrachtet die Zeitkomplexität eines [[Algorithmus]]. Da die Zeit zur Ausführung eines Algorithmuses von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine Betrachtung die Anzahl der [[Anweisung|Befehle]] analysiert, die ein Algorithmus zur Lösung eines gegebenen Problems benötigt. Die Lösung eines Problems mit Hilfe eines gegebenen Algorithmus ist abhängig von der Eingabe. Die Eingabe wird auch als Problemgröße bezeichnet. | ||
Die Analyse für kleine Eingabemengen ist häufig nicht so bedeutsam, weil für diesen Fall auch schwach konzipierte [[Algorithmus|Algorithmen]] befriedigende Ergebnisse liefern. Wichtiger sind die Betrachtungen für sehr große Problemgrößen und einer ungünstigen Anordnung der Werte (worst-case). Dabei wird von der asymptotischen [[Programmausführung|Laufzeit]] gesprochen und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Soll z.B. eine Folge von Zahlen [[Sortieren|sortiert]] werden, dann betrachtet man eine theoretisch unendliche lange Folge von Zahlen. | |||
Lässt sich ein Algorithmus mathematisch durch die Funktion beschreiben, so gilt: <math>f(x)=1/x+x</math> | |||
Die rot dargestellte Funktion<math> \color{Red}{f(x) = 1/x + x} </math>nähert sich für große x der grün dargestellte Asymptote <math> \color{green}{g(x)} </math> an. | |||
Die Laufzeit wird in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n asymptotisch unter Verwendung der Landau-Notation(Groß-O-Notation) abgeschätzt. | |||
In der Praxis ist die Laufzeitanalyse interessant, weil hierdurch entschieden werden kann, ob ein Programm bei anwachsender Eingabemenge wirtschaftlich betrieben werden kann. | |||
Version vom 20. Februar 2026, 09:21 Uhr
Einführung
Die Laufzeitanalyse betrachtet die Zeitkomplexität eines Algorithmus. Da die Zeit zur Ausführung eines Algorithmuses von der Hardwareausstattung des Zielsystems abhängt, wird für eine allgemeine Betrachtung die Anzahl der Befehle analysiert, die ein Algorithmus zur Lösung eines gegebenen Problems benötigt. Die Lösung eines Problems mit Hilfe eines gegebenen Algorithmus ist abhängig von der Eingabe. Die Eingabe wird auch als Problemgröße bezeichnet.
Die Analyse für kleine Eingabemengen ist häufig nicht so bedeutsam, weil für diesen Fall auch schwach konzipierte Algorithmen befriedigende Ergebnisse liefern. Wichtiger sind die Betrachtungen für sehr große Problemgrößen und einer ungünstigen Anordnung der Werte (worst-case). Dabei wird von der asymptotischen Laufzeit gesprochen und meint damit, in Anlehnung an eine Asymptote, das Zeitverhalten des Algorithmus für eine potenziell unendlich große Eingabemenge. Soll z.B. eine Folge von Zahlen sortiert werden, dann betrachtet man eine theoretisch unendliche lange Folge von Zahlen.
Lässt sich ein Algorithmus mathematisch durch die Funktion beschreiben, so gilt: [math]\displaystyle{ f(x)=1/x+x }[/math]
Die rot dargestellte Funktion[math]\displaystyle{ \color{Red}{f(x) = 1/x + x} }[/math]nähert sich für große x der grün dargestellte Asymptote [math]\displaystyle{ \color{green}{g(x)} }[/math] an.
Die Laufzeit wird in Abhängigkeit von der Länge n der Eingabe angegeben und für immer größer werdende n asymptotisch unter Verwendung der Landau-Notation(Groß-O-Notation) abgeschätzt.
In der Praxis ist die Laufzeitanalyse interessant, weil hierdurch entschieden werden kann, ob ein Programm bei anwachsender Eingabemenge wirtschaftlich betrieben werden kann.