Ein Algorithmus ist eine eindeutig ausführbare und endlich beschreibbare Verarbeitungsvorschrift, die eine Klasse von Problemen löst (vgl. Fachkonzept - Algorithmus).

Ein Algorithmus liefert also Lösungen für eine Vielzahl von analogen Problemstellungen. So werden Sortieralgorithmen nicht nur für eine einzige Liste konzipiert, sondern so, dass sie auf Listen beliebiger Länge anwendbar sind.

Zur Beurteilung eines Algorithmus werden der Zeit- und Speicheraufwand genauer betrachtet. Es ist klar, dass der Zeit- und Speicheraufwand in der Regel vom Umfang der zu verarbeitenden Daten abhängt. Bei einem Sortiervorgang beispielweise steigen Zeit- und Speicheraufwand mit der Anzahl der zu sortierenden Datensätze.

Der Umfang der zu verarbeitenden Daten wird mit dem Begriff Problemgröße erfasst.

Betrachten wir zunächst einen Algorithmus (bzw. eine geeignete Implementierung) zur Lösung des Sortierproblems:

int[] sortiere(int[] liste) {
  for (int bereichsGrenze = 0; bereichsGrenze < liste.length; bereichsGrenze++) {
    int kleinstes = bereichsGrenze;
 
    for (int i = bereichsGrenze; i < liste.length; i++) {
      if (liste[i] < liste[kleinstes]) {
        kleinstes = i;
      }
    }
 
    int tmp = liste[bereichsGrenze];
    liste[bereichsGrenze] = liste[kleinstes];
    liste[kleinstes] = tmp;
  }
 
  return liste;
}

Bei der Ausführung des Algorithmus (bei vorgegebener Problemgröße) spielt es eine Rolle, wie viele Operationen ausgeführt werden müssen. Operationen sind im vorliegenden Algorithmus u.a. das Ausführen eines Vergleichs und das Ausführen einer Zuweisung. Als Kostenmaß zur Beschreibung des zeitlichen Aufwands könnte man also die Gesamtanzahl der auszuführenden Vergleiche und Zuweisungen wählen.

Eine solche Festlegung des Kostenmaßes würde von folgender Vereinfachung ausgehen: Alle Vergleiche und Zuweisungen liefern denselben Beitrag zur Ausführungszeit. Ein Vergleich von Indexwerten (wie i < liste.length) würde als gleichwertig mit einem Vergleich von Datenwerten (wie liste[i] < liste[kleinstes]) behandelt. Wenn die zu sortierende Liste nur Zahlen verwaltet, mag das angemessen sein. Wenn die Liste aber komplexere Datensätze wie z.B. Strings verwaltet und der Vergleich dieser Datensätze aufwendig ist, dann ist der Gleichwertigkeitsansatz sicher nicht sinnvoll.

Bei der Festlegung eines Kostenmaßes müssen also Annahmen über den Aufwand der verschiedenen auszuführenden Operationen gemacht werden. Zwei ganz unterschiedliche Wege kann man dabei bestreiten. Ein Weg besteht darin, unterschiedliche Aufwände von Operationen möglichst genau zu erfassen und im Kostenmaß zu berücksichtigen. Ein anderer Weg beschränkt sich darauf, dominante Operationen auszuwählen und die Kosten nur grob abzuschätzen. Wir werden hier den zweiten Weg beschreiten.

Wenn man den Vergleich von Datensätzen als dominate Operation beim Sortieren ansieht, dann lässt sich das folgende Kostenmaß für Sortieralgorithmen festlegen: Alle Datensatzvergleiche werden als gleichaufwendig angesehen (egal wie die Daten im Detail beschaffen sind) und daher nur gezählt. Alle anderen Operationen werden nicht weiter berücksichtigt. Mit dieser Festlegung erhält man die folgende Kostenfunktion $T(n)$ zur Beschreibung der Zeitkomplexität beim Sortieren:

• Problemgröße $n$: Anzahl der Datensätze (Listenelemente)
• Kosten $T(n)$: Anzahl der Datensatzvergleiche bei der Ausführung des Algorithmus bei einer Problemgröße $n$

Folgende Begriffe werden bei der Aufwandsmodellierung benutzt.

Bei der Beschreibung der Zeitkomplexität mit Hilfe einer Kostenfunktion werden in der Regel eine Reihe von Vereinfachungen vorgenommen sowie Annahmen gemacht. Die Festlegung einer Kostenfunktion kann somit als eine Form der Modellierung angesehen werden, weil hier ein Berechnungsmodell entwickelt werden muss, das den Berechnungsaufwand vereinfachend beschreibt.

Wie bei jeder Modellierung kann das entwickelte Modell mehr oder auch weniger geeignet sein, um die zu beschreibende Wirklichkeit darzustellen. Bei der Modellierung der Zeitkomplexität kommt es darauf an, "richtige" Annahmen über den Aufwand bestimmter, im Algorithmus vorkommender Operationen zu machen.

Wir betrachten die bereits eingeführten Algorithmen zur Lösung des Sortierproblems. Ziel ist es, die Kosten bei der Ausführung der Algorithmen abzuschätzen.

Als Problemgröße wählen wir die Anzahl n der Datensätze (Listenelemente). Die Kosten T(n) sollen durch die Anzahl der Datensatzvergleiche bei der Ausführung des Algorithmus bei einer Problemgröße n erfasst werden.

Die Anzahl der Datensatzvergleiche bei der Ausführung eines Sortieralgorithmus hängt manchmal nicht nur von der Problemgröße $n$ (d.h. der Anzahl der Listenelemente) ab, entscheidend ist auch, wie stark die Liste bereits vorsortiert ist.

Bei einer Kostenanalyse unterscheidet man daher oft die folgenden Fälle:

• best case (bester Fall): der Fall, in dem bei der Ausführung des Algorithmus die wenigsten Kosten anfallen
• worst case (schlechtester Fall): der Fall, in dem bei der Ausführung des Algorithmus die meisten Kosten anfallen
• average case (durchschnittlicher Fall): eine Mittelung der Kosten über alle Fälle

Für die Praxis am wichtigsten ist meist der durchschnittliche Fall. Dieser ist aber schwer zu ermitteln. Wir konzentrieren uns hier daher auf den besten und schlechtesten Fall, wobei letzterer meist der relevantere ist.