Bester, durchschnittlicher und schlechtester Fall

Code in:JavaC#PythonJavaScript

Kurz gesagt: Der schlechteste Fall ist die meiste Arbeit, die ein Algorithmus bei einer Eingabe der Größe n leistet; ihn versprechen wir. Der durchschnittliche Fall ist die erwartete Arbeit unter einer Annahme über die Eingabe, meist dass jede Eingabe gleich wahrscheinlich ist.

Problem

Im Test ging es sofort

Der Support des Shops sucht eine Bestellung nach Nummer, wenn ein Kunde anruft. Die Bestellungen des Monats stehen in einer Liste, in der Reihenfolge, in der sie eingegangen sind. Der Kollege, der die Suche geschrieben hat, hat sie mit der Bestellung 1001 ausprobiert und gesagt: „Eine Prüfung. Es geht sofort, egal wie viele Bestellungen es sind.“

Einen Monat später beschwert sich der Support: Mal ist die Suche schnell, mal langsam. Am langsamsten ist sie, wenn sich der Kunde bei der Nummer vertut und es die Bestellung gar nicht gibt.

Beides stimmt. Dieselbe Suche macht eine Prüfung oder macht alle. Wie schnell ist sie also? Welche Zahl nennst du dem Support?

Die Idee

Drei Fälle eines Algorithmus

Die Zahl der Operationen hängt nicht nur von n ab, sondern auch davon, was die Eingabe ist. Deshalb schaut man sich drei Fälle an:

• der beste Fall: die Eingabe mit der wenigsten Arbeit. Hier ist die gesuchte Bestellung die erste;
• der schlechteste Fall: die Eingabe mit der meisten Arbeit. Hier ist die Bestellung die letzte oder es gibt sie nicht;
• der durchschnittliche Fall: wie viel Arbeit es im Mittel ist, wenn die Eingaben einer Regel folgen, meist „jede ist gleich wahrscheinlich“.

Der Kollege hat den besten Fall gemessen und O(1) gesagt. Aber die lineare Suche ist O(n): Bei n Bestellungen können es n Prüfungen sein.

Sieh es dir an

Die Suche mit Zähler

Die Suche prüft die Bestellungen eine nach der anderen und hört auf, sobald sie die Nummer findet:

let checks = 0;

function findOrder(ids, wanted) {
  for (let i = 0; i < ids.length; i++) {
    checks++;
    if (ids[i] === wanted) {
      return i;
    }
  }
  return -1;
}

report setzt den Zähler zurück, sucht und gibt die Position (-1, wenn es die Bestellung nicht gibt) und die Prüfungen aus:

function report(ids, wanted) {
  checks = 0;
  const at = findOrder(ids, wanted);
  console.log(`${wanted}: ${at}, Prüfungen: ${checks}`);
}

Drei Suchen in 1.000 Bestellungen: die erste, die in der Mitte und eine Nummer, die es nicht gibt:

const ids = Array.from({ length: 1000 }, (_, k) => 1001 + k);
report(ids, 1001);
report(ids, 1501);
report(ids, 999);

Ausgabe

1001: 0, Prüfungen: 1
1501: 500, Prüfungen: 501
999: -1, Prüfungen: 1000

Sieh es dir an

Eine Suche, drei Fälle

let checks = 0;

function findOrder(ids, wanted) {
  for (let i = 0; i < ids.length; i++) {
    checks++;
    if (ids[i] === wanted) {
      return i;
    }
  }
  return -1;
}

function report(ids, wanted) {
  checks = 0;
  const at = findOrder(ids, wanted);
  console.log(`${wanted}: ${at}, Prüfungen: ${checks}`);
}

const ids = Array.from({ length: 8 }, (_, k) => 1001 + k);
report(ids, 1001);
report(ids, 1005);
report(ids, 999);

Schritt für Schritt, in Worten

1. 8 Bestellungen des Monats, nummeriert von 1001 bis 1008 in der Reihenfolge ihres Eingangs. Die Suche geht vom Anfang aus, eine nach der anderen.
2. Der beste Fall: Die Bestellung ist die erste. 1 Prüfung, und die Suche ist zu Ende. Ausgabe: 1001: 0, Prüfungen: 1.
3. Die Bestellung steht in der Mitte: 5 Prüfungen, n/2 + 1. Ausgabe: 1005: 4, Prüfungen: 5.
4. Der schlechteste Fall: Diese Bestellung gibt es nicht. Die Suche prüft alle 8 und gibt erst dann -1 zurück. Ausgabe: 999: -1, Prüfungen: 8.
5. Der durchschnittliche Fall: Wird jede Bestellung gleich oft gesucht, sind die Prüfungen 1, 2, …, 8. Im Durchschnitt (1 + … + 8) / 8 = 4,5: etwa n/2. Weiterhin O(n).
6. Versprochen wird der schlechteste Fall: höchstens n Prüfungen, egal was gesucht wird. Die lineare Suche ist O(n).

Dieselben 8 Bestellungen, dieselbe Suche. Der einzige Unterschied ist, was gesucht wird.

Die Idee

Warum wir den schlechtesten Fall versprechen

Der beste Fall sagt nichts. Fast jeder Algorithmus ist schnell, wenn die Eingabe passt. Den besten Fall zu versprechen heißt, auf Glück zu setzen.

Der schlechteste Fall ist ein Versprechen. „Höchstens n Prüfungen, egal was gesucht wird.“ Mit dieser Zahl planst du: Wie viele Bestellungen kann der Support durchsuchen, bevor die Seite langsam wird. Wenn man also sagt „die lineare Suche ist O(n)“, ist der schlechteste Fall gemeint.

Der durchschnittliche Fall ist nützlich, braucht aber eine Annahme. Wird jede Bestellung gleich oft gesucht (zufällige Eingabe), ergibt die einmalige Suche nach jeder den Durchschnitt:

const ids = Array.from({ length: 1000 }, (_, k) => 1001 + k);
let total = 0;
for (const wanted of ids) {
  checks = 0;
  findOrder(ids, wanted);
  total += checks;
}
console.log("Gesamt: " + total);
console.log("Durchschnitt: " + total / ids.length);

Ausgabe

Gesamt: 500500
Durchschnitt: 500.5

(1 + 2 + … + 1.000) / 1.000 = 500,5: etwa n/2. Die Konstante ½ ändert die Klasse nicht: Auch der durchschnittliche Fall ist O(n). Aber wenn vor allem neue Bestellungen gesucht werden oder vor allem falsche Nummern, ist der Durchschnitt ein anderer. Die Annahme über die Eingabe gehört zur Antwort.

Lass die drei Fälle im Bench laufen:

• Die gesuchte Bestellung ist die erste O(1)
• Die gesuchte Bestellung ist in der Mitte O(n)
• Eine solche Bestellung gibt es nicht O(n)

Algorithmus	n = 10	n = 1.000	n = 100.000
Die gesuchte Bestellung ist die erste	1	1	1
Die gesuchte Bestellung ist in der Mitte	6	501	50.001
Eine solche Bestellung gibt es nicht	10	1.000	100.000

Der Code läuft in deinem Browser, in JavaScript. Die Zahl der Operationen ist in jeder Sprache gleich, weil der Algorithmus derselbe ist. Die Zeit hängt von der Maschine ab und dient nur zum Vergleich. „≈“ ist eine Schätzung anhand der Kurve: Ein so großes n führen wir nicht aus, damit die Seite nicht einfriert.

Genauer, für Neugierige

Die eingebaute Suche in einer Liste ist dieselbe lineare Suche. indexOf, includes und find gehen die Elemente eins nach dem anderen durch: O(n) im schlechtesten Fall. indexOf gibt -1 zurück, wenn es das Element nicht gibt, und find gibt undefined zurück.

Wenn der durchschnittliche und der schlechteste Fall sehr verschieden sind. Manche Algorithmen sind fast immer schnell und werden bei seltenen Eingaben viel langsamer. Quicksort ist im Durchschnitt O(n log n) und wird bei schlechter Wahl des Pivots O(n²) (das siehst du in der Lektion zu Quicksort). Eine Hashtabelle findet im Durchschnitt mit einem Schritt, und mit n, wenn alle Schlüssel im selben Bucket landen (das Modul „Datenstrukturen“). Dort nennt man beide Fälle, weil beide wichtig sind.

Probier es aus

Sag die Ausgabe voraus

Sechs Bestellungen, drei Suchen. Wie viele Prüfungen gibt das Programm aus?

const ids = [1001, 1002, 1003, 1004, 1005, 1006];
for (const wanted of [1004, 1006, 1010]) {
  checks = 0;
  findOrder(ids, wanted);
  console.log(checks);
}

Antwort

3 / 5 / 6

4 / 6 / 0

4 / 6 / 6

Prüfen

Probier es aus

Finde den Fehler

Jemand schreibt die Suche so:

function findOrder(ids, wanted) {
  let found = -1;
  for (let i = 0; i < ids.length; i++) {
    checks++;
    if (ids[i] === wanted) {
      found = i;
    }
  }
  return found;
}

const ids = Array.from({ length: 8 }, (_, k) => 1001 + k);
report(ids, 1001);
report(ids, 1005);
report(ids, 999);

Ausgabe

1001: 0, Prüfungen: 8
1005: 4, Prüfungen: 8
999: -1, Prüfungen: 8

Sie findet die richtige Position, aber jede Suche macht 8 Prüfungen. In welcher Zeile steckt der Fehler?

Wähle die Zeile mit dem Fehler.

1function findOrder(ids, wanted) {2 let found = -1;3 for (let i = 0; i < ids.length; i++) {4 checks++;5 if (ids[i] === wanted) {6 found = i;7 }8 }9 return found;10}

Prüfen

Übung

Neue Bestellungen werden am häufigsten gesucht

Löse die Aufgabe in deinem Editor.

Suche vom Ende. Der Support sucht fast immer Bestellungen der letzten Tage. Schreibe findLatest, das vom Ende zum Anfang sucht und die Prüfungen zählt, und lass es in report für 1.000 Bestellungen mit den Nummern 2000 (die letzte), 1001 (die erste) und 999 (gibt es nicht) laufen:

Ausgabe

2000: 999, Prüfungen: 1
1001: 0, Prüfungen: 1000
999: -1, Prüfungen: 1000

Was ist jetzt der beste Fall? Und der schlechteste? Hat sich die Klasse geändert?

Weitere Aufgaben

• Der Durchschnitt vom Ende. Lass das Programm für den durchschnittlichen Fall mit findLatest laufen. Warum ist der Durchschnitt derselbe?
• Falsche Nummern. Wenn die Hälfte der Suchen mit einer falschen Nummer läuft und die andere Hälfte gleichverteilt ist, wie viele Prüfungen sind es im Durchschnitt bei 1.000 Bestellungen?
• Nach Nummer sortiert. Die Bestellungen sind nach Nummer sortiert. Wie kann die Suche früher aufhören, wenn es die Nummer nicht gibt? Wie viele Prüfungen macht sie dann für 999?

Test

Teste dich

1. Die lineare Suche findet die Bestellung schon bei der ersten Prüfung. Ist sie damit O(1)?

Nein: Das ist der beste Fall. Im schlechtesten Fall sind es n Prüfungen, also ist sie O(n)Ja, es ist ja eine PrüfungDas hängt von der Sprache ab

2. Warum nennt man meistens den schlechtesten Fall?

Weil er am einfachsten auszurechnen istWeil er ein Versprechen ist: Egal, was gesucht wird, die Arbeit ist nicht größer als dasWeil er der häufigste ist

3. Jede von 1.000 Bestellungen wird gleich oft gesucht. Wie viele Prüfungen macht die lineare Suche im Durchschnitt?

1.000Etwa 5001

4. Kunden suchen fast immer ihre neuesten Bestellungen. Wie kannst du die Suche beschleunigen, ohne den Algorithmus zu ändern?

Zweimal suchenNichts hilftVom Ende zum Anfang suchen

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Parameter und return · static: was alle Objekte teilen · Zeitkomplexität: Schritte zählen · Big-O: wie die Arbeit wächst
• Geht weiter in: Speicherkomplexität · Amortisierte Komplexität · Lineare Suche · Binäre Suche
• Aufgaben zum Thema: Komplexität