Entwickler-Ecke :: Thema anzeigen - Vergleich von sortiertem und unsortiertem Array

Truffel - Sa 29.12.07 20:10
Titel: Vergleich von sortiertem und unsortiertem Array

Hallo,
ich hab folgendes Problem:

In einem Array befinden sich 1000 Zahlen.
Wie viele Vergleiche braucht man um herauszufinden, ob sich die Zahl 517 im Feld befindet.
a) im sortierten Feld
b) im unsortierten Feld

Wäre gut, wenn ihr mir da weiterhelfen könntet, wenn möglich auch mit Begründung, dass ich das auch nachvollziehen kann ;-)

Gausi - Sa 29.12.07 20:26

Also, ich erzähl mal was, ok?

Wenn das Array unsortiert ist, was kann man dann machen, um die 517 zu finden? Stell dir vor, du hast 1000 Kartons mit je einer Zahl drin, die in einer großen Lagerhalle stehen. Wie viele Kartons musst du aufmachen, um rauszufinden, ob eine bestimmte Zahl drin ist oder nicht?

Und jetzt der sortierte Fall. Die Kartons mit den Zahlen sind sortiert, d.h. ganz links ist die kleinste Zahl, ganz rechts die größte. Wenn man jetzt zuerst den Karton in der Mitte aufmacht und guckt, was da für ne Zahl drin ist, kann man sich dann evtl. ein paar Kartons bei der Suche nach der 517 sparen? Und wie könnte man dann geschickt weitersuchen?

Truffel - Sa 29.12.07 20:28

ich geh mal davon aus, dass das 1 Feldelement mit dem 2. verglichen wird usw.
Also Feld[i-1] wird mit Feld[i] verglichen. Bei 1000 Feldelementen wären das dann 1000 Vergleiche?! Nur wie dann nach einer bestimmten Zahl gesucht werden soll (sortiert, unsortiert) verstehe ich nicht. Ich denke mal, dass ganze liegt "Binary Search" zu Grunde. Ich werde allerdings aus dem Programmcode von "Binary Search" nicht schlau.

Truffel - Mi 02.01.08 02:30

ich hab mir überlegt:

beim unsortierten Feld: im besten Fall braucht man 1 Versuch um die gesuchte Zahl zu finden, im schlechtesten Fall braucht man 1000 Versuche die Zahl zu finden. Es ist also eine Suche auf gut Glück.

beim sortierten Feld: Wenn man in der Mitte beginnt, kann man diese mittige Zahl mit der gesuchten Zahl (517) vergleichen, und dann dementsprechend sie Suche nach links oder rechts fortsetzen.

Durchschnittlich betrachtet braucht man dann im sortierten Feld nicht so viele Versuche, wie im unsortierten Feld?!

delfiphan - Mi 02.01.08 03:58

Ich weiss jetzt nicht, ob der schlechteste Fall gefragt ist, oder die durchschnittliche Anzahl Vergleiche. In der Aufgabe steht auch nicht, dass man einen bestimmten oder möglichst effizienten Algorithmus wählen soll.

Truffel hat folgendes geschrieben:

beim unsortierten Feld: im besten Fall braucht man 1 Versuch um die gesuchte Zahl zu finden, im schlechtesten Fall braucht man 1000 Versuche die Zahl zu finden

Man kann also nicht viel machen.

Truffel hat folgendes geschrieben:

beim sortierten Feld: Wenn man in der Mitte beginnt, kann man diese mittige Zahl mit der gesuchten Zahl (517) vergleichen, und dann dementsprechend sie Suche nach links oder rechts fortsetzen.

Und wenn du eine Hälfte ausgewählt hast, dann treibst du mir der Hälfte genau wieder das gleiche Spielchen: Du teilst die Hälfte wieder in zwei Hälften. Die Frage ist also: Wieviele Male muss man (im schlimmsten Fall) 1000 in zwei Hälften teilen, bis man bei einer bestimmten Zahl ist? Wie oft kann man denn 1000 durch 2 teilen bis man bei maximal 1 ist?

alzaimar - Mi 02.01.08 11:24

Die Frage ist schon falsch gestellt.

Es darf nicht heißen 'Wie viele Vergleiche benötigt man....?' sondern z.B. 'Wie viele Vergleiche benötigt man im Mittel ...'. (Huch, hat ja Delfiphan schon geschrieben)

Auf die erste Frage kann man mit 'Woher soll ich das wissen, bin ich Hellseher?' antworten. Die Antwort auf die zweite Frage hingegen kann (hier) mathematisch korrekt gegeben werden.

So, jetzt bis Du wieder dran: Wie wiele Versuche benötigt man im Mittel, um eine bestimmte Zahl in einem beliebigen Array mit 4 Elementen zu finden?

In 1/4 aller Fälle befindet sich die gesuchte Zahl im 1.Karton. Ich benötige also in 1/4 aller Fälle 1 Versuch.
In 1/4 aller Fälle befindet sich die gesuchte Zahl im 2.Karton. Ich benötige also in 1/4 aller Fälle 2 Versuche.
In 1/4 aller Fälle befindet sich die gesuchte Zahl im 3.Karton. Ich benötige also in 1/4 aller Fälle 3 Versuche.
In 1/4 aller Fälle befindet sich die gesuchte Zahl im 4.Karton. Ich benötige also in 1/4 aller Fälle 4 Versuche.

Quelltext

1:
2:
3:
4:
5:
6:

  1/4 * 1
+ 1/4 * 2
+ 1/4 * 3
+ 1/4 * 4
==========
  1/4 * 10 = 2,5

Die mittlere Anzahl an Versuchen, um eine Zahl in einem insortierten Array mit 4 Elementen zu finden, ist 2,5.

Gausi - Mi 02.01.08 11:34

Naja...in der Regel fängt man bei sowas aber mit der Worst-Case-Anzahl an. Das ist nämlich in der Regel wesentlich einfacher ;-). Bei der Mid-Case-Analyse muss man in der Regel auch weitere Annahmen machen, wie z.B. dass die Position des gesuchten Elements gleichverteilt ist.

Wie viele man im sortierten Fall maximal braucht, weiß ich grad nicht auswendig, aber ich glaube, das war ganz logisch :mrgreen:.

alzaimar - Mi 02.01.08 19:24

Hi,

ich wollte hier nicht auf die doch relativ komplexe Aufwandsanalyse, insbesondere bei rekursiven Algorithmen, zu denen die binäre Suche gehört, eingehen.

Gausi hat folgendes geschrieben:

... muss man in der Regel auch weitere Annahmen machen, wie z.B. dass die Position des gesuchten Elements gleichverteilt ist.

Auf die (Gleich-)Verteilung bin ich in meinem Beispiel eingegangen.

Übrigens sind ähnliche Überlegungen auch bei der binären Suche sinnvoll.

Wie hoch ist die Wahrscheinlichkeit, das das gesuchte Element das in der Mitte ist? Diese Frage für jede Unterteilung zu beantworten, bedeutet 90% der Aufgabe gelöst zu haben.

Truffel - Do 03.01.08 02:56

Ich habe die Augabenstellung fast wörtlich übernommen.
Da also nicht nach dem besten bzw. dem schlechtesten Fall im unsortierten Feld gesucht ist, muss man wohl beide Fälle angeben. Minimal: 1, Maximal: 1000 (wobei dann immer noch nicht gesagt ist, ob sich die Zahl überhaupt darin befindet).
Hierfür ist also die Antwort von alzaimar wohl am besten: 'Bin ich Hellseher?' ^^

@alzaimar:
Du bist in deinem Beispiel davon ausgegangen das sich diese bestimmte Zahl im Array befindet. Das muss aber ja in meinem Beispiel nicht der Fall sein, sie kann darin sein, muss aber nicht.

Dragonclaw - Do 03.01.08 03:58

Bei der binären suche würde das dann so aus sehen

best case = 1 <= Die gesuchte Zahl ist genau die erste ermittelte Mitte
worst case = ???

Spielen wir ganze mal mit 10 Feldern durch in dem die Zahlen von 1 bis 10 untergebracht werden

Gesucht ist die Zahl 3

Beim ersten Mal ist die Mitte 5. Da 3 < 5 ist wird der rechte Teil ausgeschlossen. Die neue Mitte ist 2
Check ob links oder rechts weiter suchen, da 3 > 2 wird rechts weiter gesucht. Hier startet dann der neue Suchaufruf. Die Mitte ist jetzt 3. Also wurde die Zahl gefunden, 3 Suchaufrufe

Als letzes muss noch der Fall untersucht werden wenn die Zahl nicht im Feld ist.

Wieder ist die 3 gesucht, allerdings sind jetzt nicht mehr die Zahlen von 1 bis 10 im Feld sondern
1 2 4 5 6 7 8 9 10 11

Die Mitte ist hier die 6. Da 3 < 6 wird rechts wieder ausgeschlossen zur neuen Mitte wird die 4, wieder der Check 3 < 4 also wird wieder rechts ausgeschlossen. Die neue Mitte ist 1, der Check liefert das 3 > 1 ist, also wird links ausgeschlossen. und die neue Mitte ist 2. 2 ist kleiner als 3, eigentlich sollte die Mitte neu gesetzt werden, es gibt aber keine Zahlen mehr zum suchen, also bricht der Algo ab und berichtete "Zahl nicht gefunden".Damit hätten wir dann auch den worst case, nämlich 4 Suchaufrufe.

Dafür gibt es aber auch eine Formel, man muss das also nicht für 1000 durchspielen.
Und zwar geht das ganze über die 2er Potenzen, man such sich immer die kleinst mögliche 2er Potenz die allerdings größer ist als die Anzahl der Felder. Der Exponent gibt dann den Worstcase an.

Für 10 Felder 2^4 = 12 , 12 ist görßer als 10. Der Worstcase ist also 4
Für 100 Felder 2^7 = 128, Da ist der Worstcase also 7.
Für 1000 Felder ist der Worstcase also???

alzaimar - Do 03.01.08 10:33

Truffel hat folgendes geschrieben:

@alzaimar:
Du bist in deinem Beispiel davon ausgegangen das sich diese bestimmte Zahl im Array befindet. Das muss aber ja in meinem Beispiel nicht der Fall sein, sie kann darin sein, muss aber nicht.

Ich habe ja auch den mittleren Aufwand berechnet, und nicht den maximalen. Da sich mein Ergebnis mit dem mathematischen Aufwand deckt, vermute ich eher einen Denkfehler in deinem Einwand (der aber auf den 1.Blick berechtigt erscheint). Überlege mal: Ob ich nun nach 4 Vergleichen die Zahl finde oder nicht, kommt doch aufs Gleiche raus. :wink:

Zur binären Suche (sei n die Anzahl der Elemente in dem Array und die 'Mitte' das Element an der Position (l+r)/2 ):
Die Wahrscheinlichkeit, das die Zahl nach der 1.Teilung in der Mitte ist, ist 1/n.
Die Wahrscheinlichkeit, das die Zahl nach der 2.Teilung in der Mitte ist, ist 2/n. Denn die Zahl kann ja in der linken oder der rechten Hälfte vorkommen.
Die Wahrscheinlichkeit, das die Zahl nach der 3.Teilung in der Mitte ist, ist 4/n. Denn wir haben 4 Teilabschnitte, bei denen wir die Zahl jeweils in der Mitte sein kann.
...
usw.

Nun müssen wir noch klären, wie viele Vergleiche man pro Durchlauf bei einer binären Suche benötigt. Wenn das Element gefunden wurde (1 Vergleich), sind wir fertig. Wenn sich das Element in der linken Hälfte befinden (noch ein Vergleich), müssen wir links weitersuchen, sonst rechts.

Wir benötigen in 1/n aller Fälle 1 Vergleich.
Wir benötigen in 2/n aller Fälle 2+1 Vergleiche. (1.Teilung: 2 Vergleiche, 2.Teilung 1 Vergleich)
Wir benötigen in 4/n aller Fälle 2+2+1 Vergleiche.
...

Delete - Do 03.01.08 16:50
Titel: Re: Vergleich von sortiertem und unsortiertem Array

Truffel hat folgendes geschrieben:

wenn du es sicher finden willst, brauchst du im fall

a) 6,90775579 vergleiche
und im fall
b) 1000 vergleiche

<HTH>

Gausi - Do 03.01.08 16:56
Titel: Re: Vergleich von sortiertem und unsortiertem Array

Grenzgaenger hat folgendes geschrieben:

wenn du es sicher finden willst, brauchst du im fall

a) 6,90775579 vergleiche

Damit kommst du nicht aus. Man muss schon den 2er-Logarithmus nehmen, wenn man hier die konkrete Anzahl haben will, nicht den natürlichen ;-). Da 2^9 < 1000 < 2^10 braucht man wohl im schlimmsten Fall 10 Vergleiche.

Delete - Do 03.01.08 17:00
Titel: Re: Vergleich von sortiertem und unsortiertem Array

Gausi hat folgendes geschrieben:

Grenzgaenger hat folgendes geschrieben:

wenn du es sicher finden willst, brauchst du im fall

a) 6,90775579 vergleiche

hast recht, hab da geschlampert

zu a) 9,965784285 vergleiche

wer's nicht glaubt, kann da mal schnell nachrechnen ... :-)

alzaimar - Do 03.01.08 20:52

Grenzgaenger hat folgendes geschrieben:

wenn du es sicher finden willst, brauchst du im Fall
a) 6,90775579 vergleiche
und im fall
b) 1000 vergleiche

Nein, denn wenn die gesuchte Zahl im Fall a) an der 500.ten Stelle oder im Fall b) an der 1.Stelle ist, benötige ich nur jeweils einen Vergleich, um es sicher zu finden.

Grenzgaenger hat folgendes geschrieben:

hast recht, hab da geschlampert
zu a) 9,965784285 vergleiche
wer's nicht glaubt, kann da mal schnell nachrechnen ... :-)

Kommt drauf an. Wenn man einen Vergleich benötigt, um auf Gleichheit zu prüfen und einen Vergleich, um zu entscheiden, ob man links oder rechts weiter suchen muss, benötigt man um die 17 Vergleiche.

Du rechnest ja jeweils nur den Worst-Case aus, aber das ist -soweit ich das verstanden habe- nicht die Aufgabenstellung. Wobei der Unterschied zwischen 'im Mittel' und 'im schlechtesten Fall' im Falle der Binärsuche keinen großen Unterschied macht (mal log(n)/log(n-1)), wohl aber bei der linearen Suche (mal 2).

Hmm... Die Aufgabenstellung bzw. die Frage ist aber auch blöd, bzw. gar nicht zu beantworten, denn wo ist denn die 517 überhaupt?

Truffel - Fr 04.01.08 00:37

Nur mal so eine Zusatzinfo:
Hab vorhin nachmal nachgeschaut: die Aufgabenstellung ist genauso, wie ich sie hier rein geschrieben hab. Ich bin in der 12. Klasse Informatik GK. Wir haben in der Woche ca. 135 Minuten Informatikunterricht.
Ich nehme mal an, dass ihr alle schon fortgeschritten seit. Sowie ich das sehe, soll diese "kleine" Augabe einfach nur eine Einführung in das Prinzip der binären Suche sein.
Scheinbar seit ihr euch hier auch nicht ganz so einig, was natürlich keine Kritik sein soll.
Ich kann mir nicht vorstellen, dass der Lehrer bei dieser Aufgabe irgendwas mit nem Logarithmus voraussetzt. Scheinbar muss die Aufgabenstellung doch etwas unpassend formuliert sein...

Delete - Fr 04.01.08 02:53

delfiphan hat folgendes geschrieben:

Ausserdem steht nichts darüber, welche Algorithmen untersucht werden müssen. Aber meine Glaskugel meint, dass es um die maximale Anzahl geht und der bestmögliche Suchalgorithmus bei unbekanntem Array untersucht werden soll, und die Zahl 517 keine weitere Bedeutung hat ;)

tja, dann kann man ja auch in 'n sortierten arrary sequentiell suchen, dann lautet die neue antwort:

a) 1000
b) 1000

um sie sicher zu finden :-)

mal davon abgesehen. hier können wir nur raten, welchen stoff dein prof im unterricht durchgenommen hat und somit die mögliche lösung bestimmt. mit unseren antworten kannst du daher das selbe anfangen, wie wir mit deiner fragestellung... und 'n guter blick in die kristallkugel ist da wohl für beide seiten sinnvoller ... :-)

alzaimar - Fr 04.01.08 17:21

Grenzgaenger hat folgendes geschrieben:

tja, dann kann man ja auch in 'n sortierten arrary sequentiell suchen, dann lautet die neue antwort:
a) 1000
b) 1000
um sie sicher zu finden :-)

Falsch, sie lautet
a) 3000
b) 3000

wg.

I. Vielleicht hab ich beim ersten Durchlauf was übersehen?
II. Aller guten Dinge sind 3!

Andererseits müsste die Antwort eigentlich lauten:

a) 42
b) 42

wg. Sechs mal Neun

Truffel - Fr 04.01.08 19:07

tja, wie das gemeint ist, kann ich leider auch nicht sagen.
vorher sind wir immer von einem array mit 20 feldelementen ausgegangen.
die zahlen, die vorkamen, wurde mit "random(200)" generiert, dh. sie waren nicht größer als 200.

ich würde dann auch mal auf die glaskugel von delphifan vertrauen :D
also immer vom worst-case ausgehen...

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!