Komplexität

Die Komplexitätstheorie unterscheidet zwischen räumlicher und zeitlicher Komplexität. Gemeint ist damit der Aufwand, welcher nötig ist, um ein bestimmtes Ziel zu erreichen. Ziel kann dabei auch offene Variablen haben. Weiter unterscheidet man zwischen kleinster, mittlerer und maximaler Komplexität.

Z.B. ist die Komplexität des Sortierens mindestens der Anzahl der Elemente, weil selbst, wenn die Reihe bereits sortiert ist, muss man jedes Element betrachten, um diesen Sachverhalt zu realisieren.