MINT üben

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.
Merke

Kostenmodell: Statt zu stoppen, zählt man Schritte: Jede elementare Anweisung (Zuweisung, Vergleich, Zugriff a[i]) kostet einen Schritt.

Laufzeitfunktion: \(T(n)\) = Zahl der Schritte in Abhängigkeit von der Problemgröße \(n\) (meist Länge der Reihung).

Schleifen zählen: Sequenz: addieren. Zählschleife: Rumpf \(n\)-mal, Bedingung \((n+1)\)-mal. Verzweigung: im ungünstigsten Fall den teureren Zweig zählen.

Fälle: bester, ungünstigster, durchschnittlicher Fall — ohne Angabe meint man den ungünstigsten.

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
Merke

Schleife: Bei \(n\) Durchläufen wird der Rumpf \(n\)-mal ausgeführt.

Verschachtelt: Der innere Rumpf läuft für jeden Durchlauf der äußeren Schleife. Unabhängige Schleifen: \(n\cdot n\). Innere Schleife ab i + 1: \(\dfrac{n(n-1)}{2}\).

Halbieren: Halbiert eine Schleife ihre Variable, läuft sie nur \(\lfloor\log_2 n\rfloor\)-mal.

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