%path = "Mathematik/Informatik/Komplexität" %kind = kinda["Texte"] %level = 9
Komplexität
Um auf einen Wert einer Variable zu verweisen, braucht es Speicher. Ergibt sich der Wert jedoch aus Werten anderer Variablen, erpart man sich diesen Speicher. Das ist ein Grund, warum Funktionen wichtig sind.
Andererseits muss man dann Berechnungen machen, um vom Wert einer Variable auf den Wert der anderen Variable zu schließen. Das braucht Zeit.
Komplexität gibt das Ausmaß der benötigten Resourcen wieder. Wenn viel Zeit gebraucht wird, dann ist die Zeitkomplexität hoch. Wenn viel Speicher bebraucht wird, dann ist die Speicherkomplexität oder Raumkomplexität hoch.
Da Computer unterschiedlich schnell sind, gibt man nur die Größenordnung in Abhängigkeit von der Kardinalität \(n\) der Eingabemenge in der O-Notation an, etwa \(O(n^2)\).