Zeit- und Platzklassen: Unterschied zwischen den Versionen
Css (Diskussion | Beiträge) |
Css (Diskussion | Beiträge) |
||
Zeile 2: | Zeile 2: | ||
Weiterhin betrachtet man üblicherweise nicht die absolute Zeit bzw. den absoluten Platz, den ein Algorithmus braucht, sondern dessen '''Asymptotik''', die man üblicherweise in Landau-Notation angibt. Der Grund ist, dass es verschiedene Maschinenmodelle gibt, aber die Asymptotik in den meisten realisierbaren Maschinenmodellen gleich ist (wir lassen an der Stelle mal Quantencomputer außen vor). | Weiterhin betrachtet man üblicherweise nicht die absolute Zeit bzw. den absoluten Platz, den ein Algorithmus braucht, sondern dessen '''Asymptotik''', die man üblicherweise in Landau-Notation angibt. Der Grund ist, dass es verschiedene Maschinenmodelle gibt, aber die Asymptotik in den meisten realisierbaren Maschinenmodellen gleich ist (wir lassen an der Stelle mal Quantencomputer außen vor). | ||
+ | |||
+ | == Algorithmen == | ||
Wir sagen, ein Algorithmus $A(x)$ hat die (Zeit-)Komplexität ${\cal O}(f)$, oder meistens einfach "ist ${\cal O}(f)$", wenn es eine Funktion $g$ gibt, sodass die Zeit, die $A(x)$ braucht, höchstens $g(|x|)$ Schritte sind, wobei $|x|$ die Länge von $x$ ist, sodass $g\in{\cal O}(f)$. | Wir sagen, ein Algorithmus $A(x)$ hat die (Zeit-)Komplexität ${\cal O}(f)$, oder meistens einfach "ist ${\cal O}(f)$", wenn es eine Funktion $g$ gibt, sodass die Zeit, die $A(x)$ braucht, höchstens $g(|x|)$ Schritte sind, wobei $|x|$ die Länge von $x$ ist, sodass $g\in{\cal O}(f)$. | ||
Zeile 10: | Zeile 12: | ||
Es ist auf jeden Fall bei solchen Angaben immer wichtig, zu wissen, was genau gemeint ist, sonst kann es schnell zu Missverständnissen kommen. | Es ist auf jeden Fall bei solchen Angaben immer wichtig, zu wissen, was genau gemeint ist, sonst kann es schnell zu Missverständnissen kommen. | ||
+ | |||
+ | == Sortierung von Listen == | ||
+ | |||
+ | Wir wollen uns ein praktisches Beispiel anschauen: Das Sortieren von Listen. | ||
+ | |||
+ | == Klassen == | ||
+ | |||
+ | Vielen Algorithmen sieht man ihre Komplexität direkt an, oder man kommt durch ein wenig Nachdenken darauf. Andererseits kann es zum selben Problem viele verschiedene Algorithmen mit unterschiedlichem Laufzeitverhalten geben. | ||
== Polynomielle Zeit == | == Polynomielle Zeit == |
Version vom 16. August 2018, 14:30 Uhr
Es gibt zwei wesentliche Fragen, die man sich über ein Programm idR stellt: Wie viel Zeit benötigt es, und wie viel Speicher braucht es dafür. Üblicherweise berechnet man den maximalen Platz bzw. die maximale Zeit in Abhängigkeit der Länge der Eingabe.
Weiterhin betrachtet man üblicherweise nicht die absolute Zeit bzw. den absoluten Platz, den ein Algorithmus braucht, sondern dessen Asymptotik, die man üblicherweise in Landau-Notation angibt. Der Grund ist, dass es verschiedene Maschinenmodelle gibt, aber die Asymptotik in den meisten realisierbaren Maschinenmodellen gleich ist (wir lassen an der Stelle mal Quantencomputer außen vor).
Inhaltsverzeichnis
Algorithmen
Wir sagen, ein Algorithmus $A(x)$ hat die (Zeit-)Komplexität ${\cal O}(f)$, oder meistens einfach "ist ${\cal O}(f)$", wenn es eine Funktion $g$ gibt, sodass die Zeit, die $A(x)$ braucht, höchstens $g(|x|)$ Schritte sind, wobei $|x|$ die Länge von $x$ ist, sodass $g\in{\cal O}(f)$.
Oft schreibt man auch explizit hin, in Abhängigkeit von was genau die Klasse ist, also in unserem Fall ${\cal O}(f(|x|))$. Meistens redet man aber über Probleme mit nur einer Eingabe, und dann ist üblicherweise die Länge der Eingabe gemeint.
Ist die Eingabe eine Zahl, dann meint man normalerweise deren Länge in einem Stellenwertsystem, zum Beispiel dem Dezimalsystem.
Es ist auf jeden Fall bei solchen Angaben immer wichtig, zu wissen, was genau gemeint ist, sonst kann es schnell zu Missverständnissen kommen.
Sortierung von Listen
Wir wollen uns ein praktisches Beispiel anschauen: Das Sortieren von Listen.
Klassen
Vielen Algorithmen sieht man ihre Komplexität direkt an, oder man kommt durch ein wenig Nachdenken darauf. Andererseits kann es zum selben Problem viele verschiedene Algorithmen mit unterschiedlichem Laufzeitverhalten geben.