Was hat das mit unserer Suche zu tun?

Unsere Datenstrukturen sind nicht auf binaereSuche ausgelegt

Du fragst dich nun vielleicht, was diese ganzen Datenstrukturen mit unserer ursprünglichen Problemstellung, der Suche eines Objekts in einer Datenmenge zu tun hat.

Wir wollen uns dafür einige Beispiele anschauen:

Aufgabe 1

Überlege im Folgenden, wieviele Schritte benötigt werden, um ein gegebenes Objekt auf der sortierten Liste 1, 5, 9, 11, 23, 47, 55, 56, 99 mit unserem binären Suchalgorithmus zu finden. Dazu zähle allerdings nicht nur die Anzahl der Vergleiche, die der Algorithmus durchführen muss, sondern zähle separat auch die Anzahl der Listenelemente, die durchlaufen werden müssen.

Das heißt, dass Du am Ende die Anzahl der Vergleiche und die Anzahl der zu durchlaufenen Listenelemente angibst. Damit verlassen wir die Vereinfachung, dass nur Vergleiche Zeit benötigen. Auch Listenelemente einfach zu durchlaufen kostet Rechenleistung und Zeit, wenn auch gewiss weniger, als ein Vergleich. Letzterem tragen wir Rechnung, indem wir die beiden Dinge separat zählen.

(a)Finde das Objekt 56 in einer einfach verketteten Liste.

(b)Finde das Objekt 56 in einer doppelt verketteten Liste.

(c)Finde das Objekt 1 in einer einfach verketteten Liste.

(d)Finde das Objekt 1 in einer doppelt verketteten Liste.

Geht es noch besser, als doppelt verkettete Listen?

Du hast oben gesehen, dass die doppelt verkettete Liste in manchen Fällen schneller als die einfach verkettete Liste ist, in anderen wiederum nicht. In beiden Fällen allerdings müssen wir einige überflüssig scheinende Durchläufe durch die Liste machen, um z.B. nur schon zum Median zu kommen.

Da stellt sich natürlich die Frage, ob es nicht besser geht und wir mit weniger potentiell überflüssigen Listendurchläufen klarkommen.

Aufgabe 2

(a) Nehmen wir nun naiveSuche und wieder die Liste 1, 5, 9, 11, 23, 47, 55, 56, 99. Untersuche diese wie oben nach 1 und 56 und zähle die Anzahl der Durchläufe und die Vergleiche in einer einfach verketteten Liste.

(b) Nun das selbe mit einer doppelt verketteten Liste.

Der "Fehler" liegt in unserer Datenstruktur!

Das Problem mit unseren überflüssigen Listendurchläufen liegt nicht in unserem Algorithmus. Wir können zwar vielleicht Listendurchläufe vermeiden, wenn wir einen ansonsten zeitineffizienteren Algorithmus wählen, aber dafür brauchen wir dann mehr Vergleiche.

Das liegt daran, dass unsere Liste keine Zeiger auf die Elemente hat, die wir im Algorithmus als nächstes brauchen, sondern einfach nur auf das nächstgrößere (bzw. nächstkleinere). Wenn wir unsere Elemente also intelligenter abspeichern können, können wir vielleicht bei gleicher Anzahl an Vergleichen mit weniger, vielleicht sogar gar keinen "überflüssigen" Schleifendurchläufen auskommen.