Komplexität.md

Komplexität

Kostenanalyse

Unser Vorgehen: dominante Operation auswählen und Kosten grob ausrechnen

Problemgröße: präzise Beschreibung des Umfangs der zu verarbeitenden Daten, von dem Zeit- bzw. Speicherverhalten von Lösungsalgorithmen maßgeblich beeinflusst wird.

Kostenmaß: legt fest, in welchem Maße Operationen bei der Aufwandsbestimmung berücksichtigt werden

Kostenfunktion: ordnet der Problemgröße n die vom Algorithmus benötigten Gesamtkosten T(n) bzgl. des vorgegebenen Kostenmaßes zu

Beispiel: Problemgröße: n Listenelemente/Datensätze Kostenmaß: Anzahl der Vergleiche der Listenelemente Kostenfunktion: T(n)

Kostenanalyse Bubblesort

T_best(n) = n - 1

T_worst(n) = (n^2)/2 + n/2

T_average(n) = (n^2)/2 + n/2

Kostenanalyse Selectionsort

T_best(n) = (n - 1) + (n - 2) + ... + 1 = (n * (n - 1)) / 2 = (n^2)/2 + n/2

T_worst(n) = (n^2)/2 + n/2

T_average(n) = (n^2)/2 + n/2