Was wäre ein Beispiel für eine teure Operation bzw. eine billige Operation in einem Programm?

Bei der Bewertung der Kosten einer Operation können Faktoren wie Rechenzeit, Speicherbelegung oder der Verbrauch an menschlichen Ressourcen durch den Entwicklungsaufwand eine Rolle spielen.

Bsp 1: Eine billige Operation bezüglich der Rechenzeit ist die Änderung des Werts eines Array-Elements bei gegebenem Index. Verhältnismäßig teuer ist es, ein Array-Element am Anfang eines langen Arrays einzufügen, da alle anderen Elemente des Arrays um eine Position nach hinten verschoben werden müssen, bevor eingefügt werden kann.

Bsp 2: Einen langen String mit dem + Operator aufzubauen ist in Java bezüglich Rechenzeit und Speicherbelegung eine teure Operation. Bei jeder Konkatenation von zwei Strings wird intern ein StringBuilder-Objekt erzeugt, der String zusammengesetzt und abschließend die toString() Methode des Stringbuilders aufgerufen. Erzeugt man explizit einen Stringbuilder und führt die String-Konkatenationen mit diesem Stringbuilder durch, ist dies wesentlich billiger.

Beispiel mit Zeitmessung:

static long f1(int n) {
    long t1 = System.nanoTime();
    String s = "";
    for (int i = 0; i < n; i++) {
        s += "a";
    }
    long t2 = System.nanoTime();
    return (t2 - t1) / 1000;
}

static long f2(int n) {
    long t1 = System.nanoTime();
    StringBuilder s = new StringBuilder();
    for (int i = 0; i < n; i++) {
        s.append("a");
    }
    long t2 = System.nanoTime();
    return (t2 - t1) / 1000;
}

public static void main(String[] args) {
    for (int n = 1000; n <= 128000; n *= 2) {
        System.out.printf("n=%6d | %7dµs | %7dµs\n", n, f1(n), f2(n));
    }
}

Sowohl in der Methode f1(n) als auch in der Methode f2(n) wird ein String der Länge n durch wiederholtes Anhängen eines einzelnen Zeichens aufgebaut.

In der Methode f1() wird der +-Operator für den Aufbau des Strings verwendet.
In der Methode f2() wird der String mithilfe eines explizit erzeugten Stringbuilders aufgebaut.

Die Auswertung der Zeitmessung von f1() zeigt, dass der Aufwand bei der Konkatenation mit dem +-Operator quadratische Ordnung hat. Das heißt, bei einer Verdoppelung der Anzahl der Konkatenationen n steigt der Zeitaufwand auf das Vierfache.

Im Vergleich dazu ist der Aufwand bei der Konkatenation mit dem Stringbuilder (f2()) linear. Das heißt, bei einer Verdoppelung der Anzahl der Konkatenationen n verdoppelt sich der Zeitaufwand.

Bezüglich der Rechenzeit verbraucht f1() also wesentlich mehr Ressourcen als f2(). Bewertet man den Faktor Zeit, ist also f1() wesentlich teurer als f2().