Submitted by javafrage on Mon, 03/17/2014 - 08:27 Welchen Aufwand O() hat die binäre Suche? Welchen Aufwand O() hat die sequentielle Suche? Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken). Niveau 2 Schwierigkeitsgrad mittel Zeit 2 Minuten Antwort zu Frage 9: Binäre Suche Man benötigt maximal 4 Vergleiche. BinäreSuche - Korrektur Bei der Binären Suche liegt ein Fehler vor. Es sind lediglich 3 Vergleiche die gemacht werden. Im ersten Schritt 15 - ist richtig Im zweiten Schritt muss allerdings die 19 markiert werden anstelle der 21. Im dritten Vergleichsschritt kommt man dann direkt auf die 23 Viele Grüße! Reply Book traversal links for 10 Aufwand binäre Suche und sequentielle Suche ‹ 9 Binäre Suche Up 11 Komplexitätsbetrachtungen 4 ›
Die binäre Suche erfolgt nach dem "Teile und Herrsche" Prinzip (divide et impera) durch Teilen der zu durchsuchenden Liste. Voraussetzung: Die Folge muss steigend oder fallend sortiert sein!
Wie hast du das denn gemessen? Mit den 5 Einträgen im Array? Und mit einem Durchlauf? Diese Messung kannst du getrost vergessen (mal abgesehen von der Genauigkeit von nanoTime()). Die lineare Suche hat einen Aufwand O, die binäre Suche einen Aufwand von O(log n). Mit anderen Worten: binäre Suche ist um Längen schneller je mehr Elemente im Array sind. Lexikalische Vergleiche kann man mit der pareTo Methode vollführen: if (array[mitte]. compareTo(suchwort) < 0) {... } Gruß PS: @Saban: Deine Suche dürfte für ein leeres Array nicht funktionieren. #4 Hast recht. Ich habs jetzt schnell mal mit 2000 Elementen gesucht. Es enthielt immer nur A in der Länge des aktuellen Feldes + 1. Also A AA AAA AAAA usw. Bei ihm kam 287437. Bei mir 584162. Also war meiner um 0. 3ms langsamer, dennoch finde ich den Source um einiges übersichtlicher. Und was genaueres als nanoTime() kenne ich leider in der Größenordnung nicht. Die Methode verstehe ich irgendwie nicht. Laut Api vergleicht er einfach einen String mit einen Object, ist es kein String fliegt eine Exception?
Binäres und sequentielles Suchen im Vergleich Einführung - Binäres Suchen - Binäres vs. sequentielles Suchen 1. 2. 4 Binäres vs. sequentielles Suchen Um die Ergebnisse der letzten Seite besser bewerten zu können, betrachten wir zum Vergleich die sequentielle Suche. Sequentielles Suchen Bei der sequentiellen Suche durchlaufen wir das Feld Element für Element. Im schlechtesten Fall benötigen wir offensichtlich N Schritte zum Durchsuchen eines Feldes mit N Elementen. Für die Berechnung des durchschnittlichen Aufwands nehmen wir an, daß alle N gespeicherten Schlüsselwerte mit der gleichen Wahrscheinlichkeit 1/N gesucht werden. Dann erhalten wir für die Anzahl k der benötigten Schritte bei erfolgreicher Suche Die folgende Tabelle zeigt die Ergebnisse im Überblick. Wir unterscheiden jeweils, ob der gesuchte Schlüssel im Feld enthalten ist (erfolgreiche Suche) oder nicht (erfolglose Suche). Zusammenfassung Algorithmus Schritte im Durchschnitt Schaubild sequentielle Suche mit Erfolg ohne Erfolg binäre Suche mit Erfolg* *Näherung für große N Das Schaubild verdeutlicht, daß gerade bei großen Datenmengen binäres Suchen ein wesentlich schnelleres Auffinden der gespeicherten Daten erlaubt als sequentielles Suchen.