Komplexitätstheorie
Die Komplexität eines Algorithmus gibt den maximalen Ressourcenbedarf an und wird oft in Abhängigkeit von der Länge der Eingabe angegeben und für große Längen asymptotisch abgeschätzt. Die Komplexität eines Problems ist durch den Ressourcenverbrauch eines optimalen Algorithmus zur Lösung dieses Problems definiert. Die betrachteten Ressourcen sind meist die Anzahl der benötigten Rechenschritte oder der Speicherbedarf. Es interessiert dabe jedoch nicht der Aufwand eines konkreten Programmes auf einem bestimmten Computer, sondern das Wachstum des Ressourcenbedarfs, beim Anstieg der zu verarbeiten Daten.
|
Vorlesungsskript zur Komplexitätstheorie
|
|
Virtuelle Vorlesung zur Komplexität (Teil 1)
|
|
Virtuelle Vorlesung zur Komplexitätstheorie (Teil 2).
|
|
Material zur virtuellen Vorlesung (Teil 1 und Teil 2)
|
