MINT lernen

Operationen zählen

Wie misst man die Arbeit eines Algorithmus, ohne auf die Uhr zu sehen?

1

Zählen statt stoppen

Eine Stoppuhr misst den Rechner mit: Prozessor, Programmiersprache und Auslastung verändern die Zeit. Vergleichbar wird ein Algorithmus erst, wenn man seine Schritte zählt.

  • Kostenmodell:jede elementare Anweisung (Zuweisung, Vergleich, Zugriff a[i]) kostet einen Schritt.
  • Problemgröße:\(n\) — meist die Länge der Reihung.
  • Laufzeitfunktion:\(T(n)\) = Zahl der Schritte in Abhängigkeit von \(n\).
  • Dominierende Operation:oft genügt es, eine typische Operation zu zählen, z. B. die Vergleiche.
  • Fälle:bester, ungünstigster und durchschnittlicher Fall — ohne Angabe meint man den ungünstigsten.
static int anzahlGroesser(int[] a, int grenze) {
    int z = 0;                                  // 1-mal
    for (int i = 0; i < a.length; i++) {       // Bedingung: (n + 1)-mal
        if (a[i] > grenze) {                    // n-mal
            z++;                                // 0- bis n-mal
        }
    }
    return z;                                   // 1-mal
}
  • Sequenz:Anzahlen addieren.
  • Zählschleife:Rumpf \(n\)-mal, Bedingung \((n + 1)\)-mal — die letzte Prüfung beendet die Schleife.
  • Verzweigung:im ungünstigsten Fall den teureren Zweig zählen.
  • Beispiel oben:\(T(n) = 1 + (n + 1) + n + n + 1 = 3n + 3\) im ungünstigsten Fall (alle Werte größer), \(2n + 3\) im besten.
2

Schleifen in Schleifen

Bei verschachtelten Schleifen wird der innere Rumpf für jeden Durchlauf der äußeren Schleife ausgeführt. Entscheidend ist, wie weit die innere Schleife jeweils läuft.

Stecke bis zu drei Zählsonden an Codezeilen (anklicken oder mit ↑/↓ wählen und Enter), stelle n ein und miss mit ▶. Miss jedes Programm für n = 5, 10 und 20 und suche in der Messtabelle die Formel hinter den Zahlen.

Zählsonden

Messtabelle der Zählsonden
ProgrammnSondeZeileAusführungen
Noch keine Messung.

Halte fest: Unabhängige Schleifen multiplizieren sich (\(n \cdot n\)). Startet die innere Schleife bei i + 1, wird jedes Paar nur einmal verglichen — \(\frac{n(n-1)}{2}\). Halbiert eine Schleife ihre Variable, läuft sie nur \(\lfloor\log_2 n\rfloor\)-mal.

Herleitung:
\(V(n) = \displaystyle\sum_{i=0}^{n-2} (n - 1 - i)\)
aufstellen

Für festes i läuft j von i + 1 bis n − 1: das sind \(n - 1 - i\) Vergleiche.

\(V(n) = (n-1) + (n-2) + \ldots + 1\)
ausschreiben

i = 0 liefert \(n - 1\), i = n − 2 nur noch 1 Vergleich.

\(V(n) = \dfrac{(n-1) \cdot n}{2}\)
kleiner Gauß

Summe der Zahlen 1 bis \(n - 1\).

\(V(n) = \dfrac{n(n-1)}{2} = \dfrac{n^2}{2} - \dfrac{n}{2}\)
Ergebnis

Beispiel \(n = 10\): 45 Vergleiche, \(n = 20\): 190 — doppelte Länge, gut vierfache Arbeit.

Merke

Schleife mit \(n\) Durchläufen: Rumpf \(n\)-mal · unabhängig verschachtelt: \(n \cdot n\) · innere ab i + 1: \(\frac{n(n-1)}{2}\) · Halbieren: \(\lfloor\log_2 n\rfloor\)

3

Allgemeine Hinweise

Die Bedingung zählt einmal mehr

Eine Schleife mit \(n\) Durchläufen prüft ihre Bedingung \((n + 1)\)-mal. Wer Schleifenköpfe mitzählt, muss das beachten — beim Zählen der Vergleiche im Rumpf spielt es keine Rolle.

Eine Operation reicht oft

Für den Vergleich zweier Algorithmen genügt meist die dominierende Operation, etwa a[i] > grenze. Alle anderen Anweisungen wachsen höchstens genauso schnell.

Innere Grenze genau lesen

j = 0 oder j = i + 1, j < n oder j < i: Die Startwerte der inneren Schleife entscheiden zwischen \(n^2\) und \(\frac{n(n-1)}{2}\).

Videos