Lineare & Binäre Suche

[Krassa]

Hallo! Wir haben in der Schule Aufgaben zum obengenannten Thema bekommen, nur leider komme ich damit nicht klar, ich hoffe mir kann da geholfen werden. Ich muss die Aufgaben am Donnerstag abgeben, deswegen ist es wirklich wichtig.

also Das Telefonbuch einer Kreisstadt hat 26400 Namen.

a) Wielange dauert das Suchen eines Namens höchstens, wenn man die lexikographische Ordnung ausnutzt und binäres Suchen anwendet. Jeder Vergleich dauert etwa 1 Sekunde.

b) Man stelle sich vor, die Eintragungen seien keiner Ordnung unterworfen. Wielange dauert das Suchen nach einem Namen im Extremfall unter der Annahme, dass durchschnittlich pro Sekunde 5 Namen verglichen werden können?

c) Vergleiche die beiden Suchverfahren bei 300000 Namen und einer Zugriffszeit pro Date einer Festplatte von 0,065 Sekunden und der Vergleichszeit zweier Werte von 0,001 Sekunden.

Wenns geht könnte der Lösungsweg beschrieben werden? Ich wär euch wirklich sehr dankbar.

Greetz
Bautsen

[Jasocul]

Hier sehr gut erklärt, finde ich.

[Bernhard Geyer]

Also etwas Gedanken solltest Du dir schon machen.

Dieses Forum ist nicht dafür da deine Schulaufgaben komplett zu erledigen. Falls Du bei deinen Recherchen/Lösung an bestimmten Teilen hängen bleibst werden wir dir sicherlich gerne helfen.

[Krassa]

Ok ich denk ich habs jetzt:

Die Formel für 1) ist log(n):log2 +1 und ich habe 15,68 Vergleiche raus. Jetzt meine Frage: Ist es nicht unlogisch das eine Kommazahl rauskommt? Die Binäre Suche kann doch keinen halben Vergleich machen oder? Und: Ist die Zeit der Vergleiche auch die Zeit die benötigt wird? Weil ja jeder Vergleich 1 Sekunde dauert.

[Bernhard Geyer]

Zitat:

Zitat von Krassa

Ok ich denk ich habs jetzt:

Die Formel für 1) ist log(n):log2 +1 und ich habe 15,68 Vergleiche raus. Jetzt meine Frage: Ist es nicht unlogisch das eine Kommazahl rauskommt?

Nein. Der Wert ist ein Durchschnittswert und kann deshalb eine Kommazahl annehmen

Zitat:

Zitat von Krassa

Und: Ist die Zeit der Vergleiche auch die Zeit die benötigt wird? Weil ja jeder Vergleich 1 Sekunde dauert.

Wenn jeder Vergleich 1 Sekunde dauert, so dauert die Suche im Durchschnitt 15,68s wenn durchschnittliche 15,68 Vergleiche durchgeführt werden müssen.

[Binärbaum]

Zitat:

Zitat von Krassa

...
b) Man stelle sich vor, die Eintragungen seien keiner Ordnung unterworfen. Wielange dauert das Suchen nach einem Namen im Extremfall unter der Annahme, dass durchschnittlich pro Sekunde 5 Namen verglichen werden können?

Wenn es keine bestimmte Ordnung gibt, dann muss man im Extremfall (d.h. worst-case) alle Einträge durchsuchen, ist doch logisch oder?

MfG
Binärbaum

[atreju2oo0]

Zitat:

Zitat von Binärbaum

Wenn es keine bestimmte Ordnung gibt, dann muss man im Extremfall (d.h. worst-case) alle Einträge durchsuchen, ist doch logisch oder?

Also mir wurde in der Schule beigebracht, dass n-1 Fälle im worst-case durchsucht werden müssen. Dabei gilt natürlich die Vorraussetzung, dass der Datensatz enthalten ist.

(Das soll jetzt nicht extrem kleinlich klingen... Hat mir in der Klausur aber die 1 versaut und man kann ja mal drauf aufmerksam machen :) )

[Binärbaum]

Zitat:

Zitat von atreju2oo0

Also mir wurde in der Schule beigebracht, dass n-1 Fälle im worst-case durchsucht werden müssen. Dabei gilt natürlich die Vorraussetzung, dass der Datensatz enthalten ist.

Das stimmt schon, da man nach n-1 Fällen wüsste, dass der gesuchte Datensatz der letzte ist. Aber wer sagt denn, dass der Datensatz vorhanden sein muss? :wink:
Es könnte ja sein, dass im Telefonbuch kein Eintrag zum Namen "Zacharias Zechenpreller" (oder wonach man halt so sucht) vorhanden ist.

MfG
Binärbaum