Beispiel:
Lineare Suche im Array
i = 0; while (i < n) && (a[i] != x) { i++; }
Laufzeit: | best case | ![]() |
![]() |
![]() |
worst case | ![]() |
![]() |
![]() |
|
average case | ![]() |
![]() |
![]() |
Annahme für den average case:
Es liegt Permutation der Zahlen von bis
vor, darunter die gesuchte Zahl
Dann ist die mittlere Anzahl
Beispiel:
Suche in einem Array, bestehend aus Nullen und Einsen.
Laufzeit: | best case | ![]() |
![]() |
![]() |
worst case | ![]() |
![]() |
![]() |
|
average case |
![]() |
![]() |
![]() |
Obacht:
Alle Laufzeitangaben beziehen sich jeweils auf einen
konkreten Algorithmus (für ein Problem
)
= obere Schranke für Problem
.
Eine Aussage darüber, wie viele Schritte jeder Algorithmus für ein
Problem mindestens durchlaufen muss,
nennt man untere Schranke für Problem
.
Beispiel: naives Pattern-Matching
char[] s = new char[N]; // Zeichenkette char[] p = new char[M]; // Pattern
Frage: Taucht Pattern in Zeichenkette
auf?
boolean erfolg=false; for (i = 0; i < N - M + 1 && !erfolg; i++) { // Index in Zeichenkette for (j = 0; (j < M) && (p[j] == s[i+j]); j++); // Index im Pattern if (j == M) erfolg=true; // Erfolg }
Laufzeit best case: | ![]() |
|||
Laufzeit worst case: |
![]() |
![]() |
= | ![]() |
![]() |
= | ![]() |
Sei die Summe der Buchstaben in
und
.
Sei
und
für
.
Gesucht wird , welches
maximiert.
Bilde 1. Ableitung nach und setze auf 0: