Durchschnittliche Vergleiche bei linearer Suche

Unter der üblichen Annahme, dass das Ziel mit gleicher Wahrscheinlichkeit an jeder Position liegt, gibt er sowohl die erwartete Vergleichszahl als auch den schlechtesten Fall aus. So können Entwickler, Lernende und Prüfende die O(n)-Notation mit konkreten Zahlen für eine bestimmte Sammlungsgröße verbinden.

Verstehen Sie das Wahrscheinlichkeitsmodell des Mittelwerts

Die lineare Suche prüft Elemente der Reihe nach und endet, sobald sie das Ziel findet. Wenn ein vorhandenes Ziel mit gleicher Wahrscheinlichkeit an jeder der n Positionen liegt, kostet das Auffinden des ersten Elements einen Vergleich, das des zweiten zwei und das des letzten n. Jeder dieser Fälle hat die Wahrscheinlichkeit 1/n. Der erwartete Aufwand ist daher das arithmetische Mittel der ganzen Zahlen von 1 bis n und vereinfacht sich zu (n + 1) / 2. Geben Sie die Sammlungsgröße als n ein; der Rechner wendet genau diese Formel an. Die Annahme ist entscheidend: Das Ergebnis ist keine Schätzung aus Laufzeitmessungen, Hardware oder einer Programmiersprache. Es ist eine deterministische Vergleichszahl für eine erfolgreiche Suche bei gleichverteilten Positionen. Werden manche Positionen oder Werte häufiger gesucht, müssen ihre Wahrscheinlichkeiten getrennt gewichtet werden. Ein nicht vorhandenes Ziel bildet das Modell ebenfalls nicht ab; eine gewöhnliche lineare Suche prüft dann immer alle n Elemente.

Deuten Sie Durchschnitt und schlechtesten Fall

Das durchschnittliche Ergebnis kann ganzzahlig sein oder auf einen halben Vergleich enden. Eine Sammlung mit 100 Elementen verursacht beispielsweise erwartete 50.5 Vergleiche. Der Bruchteil bedeutet nicht, dass ein einzelner Ablauf einen halben Vergleich ausführt; er ist der langfristige Mittelwert vieler erfolgreicher Suchen mit gleichverteilten Zielpositionen. Der schlechteste Fall beträgt n, weil ein Ziel an letzter Position erst gefunden wird, nachdem jedes Element geprüft wurde. Bei einer Sammlung mit einem Element sind beide Werte eins. Mit wachsendem n nähert sich der Durchschnitt der halben Sammlungsgröße, während der schlechteste Fall die volle Größe bleibt. Beide Größen wachsen linear, weshalb die asymptotische Analyse eine erfolgreiche lineare Suche als O(n) einordnet, obwohl die Konstanten verschieden sind. Nutzen Sie den Mittelwert für Arbeitslasten, die der angegebenen Verteilung entsprechen, und den schlechtesten Fall als feste Obergrenze. Schleifenverwaltung, Speicherzugriffe, Sortierung und interne Vergleichskosten sind nicht enthalten.

Nutzen Sie das Ergebnis für Entwurfs- und Leistungsfragen

Konkrete Vergleichszahlen machen Gespräche über Algorithmen aussagekräftiger als asymptotische Notation allein. Sie können den erwarteten Aufwand der linearen Suche den Kosten einer anderen Datenstruktur gegenüberstellen, insbesondere wenn die Sammlung klein ist, selten durchsucht wird oder sich häufig ändert. Eine Hashtabelle oder ein sortierter Index kann Sucharbeit reduzieren, verursacht aber Aufbau- und Wartungskosten, die ein einfacher Durchlauf vermeidet. Dieser Rechner liefert die Durchlaufseite dieses Vergleichs, ohne eine Laufzeitmessung vorzutäuschen. Er eignet sich außerdem zum Prüfen von Aufgaben, Validieren eines Tabellenmodells, Dokumentieren einer Codeprüfung oder Erzeugen stabiler Lehrwerte. Halten Sie die Voraussetzungen beim Ergebnis fest: Das Ziel ist vorhanden, jede Position ist gleich wahrscheinlich, und die Suche beginnt vorne und endet beim ersten Treffer. Duplikate können das Modell verletzen. Bei fehlenden Zielen gelten n Vergleiche; bei ungleichmäßigen Zugriffen benötigen Sie einen gewichteten Erwartungswert.