6.2Komplexitätstheorie

Grundbegriffe der Komplexitätstheorie

Zeit und Speicher als Ressourcen – gemessen an Algorithmen und an ganzen Aufgaben, mit Sortieren als Paradebeispiel.

Leitformel
TIME(h)⊆SPACE(O(h))\mathrm{TIME}(h) \subseteq \mathrm{SPACE}\big(O(h)\big)
Lernziel

Zeit- und Platzkomplexität bestimmen, die Klassen TIME und SPACE in Beziehung setzen und Sortierverfahren nach ihrem Aufwand vergleichen.

Einheit wird geladen …