Komplexität

Unter der Komplexität eines Algorithmus versteht man seinen Ressourcenbedarf. Komplexität wird oft mittels Landau-Notation abgeschätzt.

Verwechslungsgefahr

• Die Worst Case Laufzeitkomplexität wird oft auch einfach “Komplexität” genannt
• Statt wird auch gerne einfach nur verwendet

Arten von Komplexität

Uniforme Komplexität

Bei der uniformen Komplexität (auch Einheitsmaß), entspricht jeder Befehl einem Schritt.

• Zeit-Komplexität: ist die Anzahl der Schritte, die bei der Eingabe durchführt
• Platz-Komplexität: ist die Anzahl der Speicherzellen, die bei Eingabe benutzt

Nachteile: Unterschiedliche Bit-Komplexität wird gleich gewichtet

Logarithmische Komplexität

• Gewichtung nach Bit-Komplexität
• Anstelle einer Speicherzelle wird die Bit-Länge gewichtet
• Schreibweise analog: ,

Worst Case, Average Case, Best Case

Sei ein Algorithmus mit Eingabe über einem Alphabet .

• Worst Case - Die Laufzeit im schlechtesten Fall ist
• Average Case - Die Laufzeit im Durchschnitt ist
• Best Case - Die Laufzeit im besten Fall ist