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)
T_best(n) = n - 1
T_worst(n) = (n^2)/2 + n/2
T_average(n) = (n^2)/2 + n/2
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