Minimum
-
Ich würde einfach einen binären Baum nehmen, nach dem Einfügen ist der min. Wert dann im linken Unterbaum, der max. Wert im rechten Unterbaum.
aus http://www.informatiktreff.de/materialien/sek_ii/algorithmen/baum/baum.htm
6. Baumsortieren als Sortierverfahren
Eine Anwendungsmöglichkeit des binären Suchbaums ist es, ihn zum Sortieren einer Feldstruktur zu benutzen. Nehmen wir also an, wir wollten eine Feldstruktur mit den folgenden Werten sortieren:
55 , 14 , 98 , 54 , 17 , 56 , 86 , 87 , 9 , 1 , 45 , 75
Als ersten Schritt erzeugen wir einen leeren Suchbaum.
Als zweiten Schritt sortieren wir die Zahlen der Feldstruktur der Reihe nach in diesen Suchbaum ein, unter Beachtung der für das Einfügen geltenden Bedingungen.
Der nächste Schritt ist dann, die im Suchbaum sortierten Zahlen mit einem geeigneten Durchlauf auszulesen und in die mittlerwelie geleerte Feldstruktur zurückzuschreiben. Ein binärer Suchbaum erfüllt ja die Bedingung, dass im linken Unterbaum eines Knotens niedrigere, im rechten Unterbaum höhere Zahlen stehen als in ihm selbst. Diese Eigenschaft kann man sich mit der Inorder-Traversierung zu nutze machen, da diese dann die Zahlen in der geordneten Reihenfolge ausliest.
Während des Durchlauf muss man nun nur noch die Zahlen in die Feldstruktur kopieren, die danach aufsteigend sortiert ist:
1 , 9 , 14 , 17 , 45 , 54 , 55 , 56 , 75 , 86 , 87 , 98
Weiter Möglichkeit wäre es, die Werte in einen Vector zu packen und ihn dann mit einem Sortieralgo zu sortieren. Der Baum hat den Vorteil, dass die Werte schon beim Einfügen sortiert werden.
-
Wieso würde man einen Baum verwenden wollen wenn man O(N) haben kann?
-
Plotzenhotz schrieb:
Wieso würde man einen Baum verwenden wollen wenn man O(N) haben kann?
Wo hast du O(N)?
Ausserdem ist der Aufwand für das Einfügen in einen Baum O(log n), im schlimmsten Fall O(n).
-
Einmal drüber laufen und das kleinste merken ist Laufzeit O(N), allein den Baum aufzubauen oder zu sortieren kostet O(N log N) Laufzeit. Aber hey, dafür wird ja ein Baum vewendet.
-
Jester schrieb:
Einmal drüber laufen und das kleinste merken ist Laufzeit O(N), allein den Baum aufzubauen oder zu sortieren kostet O(N log N) Laufzeit. Aber hey, dafür wird ja ein Baum vewendet.
Ich glaub du brauchst eine Auffrischung deiner Kenntnisse in Bäumen. Einfügen kostet dich O(log n), nachdem du _alles_ eingefügt hast, ist der Baum sortiert.
Ausserdem was ist wenn er dann das 2. kleinste Element braucht? Nochmal alles durchsuchen?
-
DEvent schrieb:
Jester schrieb:
Einmal drüber laufen und das kleinste merken ist Laufzeit O(N), allein den Baum aufzubauen oder zu sortieren kostet O(N log N) Laufzeit. Aber hey, dafür wird ja ein Baum vewendet.
Ich glaub du brauchst eine Auffrischung deiner Kenntnisse in Bäumen. Einfügen kostet dich O(log n), nachdem du _alles_ eingefügt hast, ist der Baum sortiert.
Ausserdem was ist wenn er dann das 2. kleinste Element braucht? Nochmal alles durchsuchen?
Lol, willst Du jetzt mit mir drüber diskutieren wie lange es dauert n Elemente in nen Baum einzufügen? Eine Einfügung kostet O(log N), N Elemente Einfügen kostet O(N log N). In O(log N) kannst Du Dir nichtmal alle Elemente anschaun.
Wenn er das kleinste und das zweitkleinste haben will (oder die k kleinsten, k Konstante), dann geht das immer noch in O(N) und man muß nicht auf O(N log N) Laufzeit hoch. Außerdem war das auch nicht die Aufgabenstellung. Er hat schließlich nach dem kleinsten Element statt nach Sortierung gefragt.
edit: selbst einfach nochmal durchsuchen ist besser als den langsameren Algorithmus zu nehmen.
-
Jester schrieb:
DEvent schrieb:
Jester schrieb:
Einmal drüber laufen und das kleinste merken ist Laufzeit O(N), allein den Baum aufzubauen oder zu sortieren kostet O(N log N) Laufzeit. Aber hey, dafür wird ja ein Baum vewendet.
Ich glaub du brauchst eine Auffrischung deiner Kenntnisse in Bäumen. Einfügen kostet dich O(log n), nachdem du _alles_ eingefügt hast, ist der Baum sortiert.
Ausserdem was ist wenn er dann das 2. kleinste Element braucht? Nochmal alles durchsuchen?
Lol, willst Du jetzt mit mir drüber diskutieren wie lange es dauert n Elemente in nen Baum einzufügen? Eine Einfügung kostet O(log N), N Elemente Einfügen kostet O(N log N). In O(log N) kannst Du Dir nichtmal alle Elemente anschaun.
Ob ein Baum sinnvoll ist kommt wohl ganz einfach drauf an was der OP konkret vorhat, nicht?
Jester schrieb:
Wenn er das kleinste und das zweitkleinste haben will (oder die k kleinsten, k Konstante), dann geht das immer noch in O(N) und man muß nicht auf O(N log N) Laufzeit hoch. Außerdem war das auch nicht die Aufgabenstellung. Er hat schließlich nach dem kleinsten Element statt nach Sortierung gefragt.
edit: selbst einfach nochmal durchsuchen ist besser als den langsameren Algorithmus zu nehmen.
Dürfte im Suchbaum beides schneller sein als nochmal komplett durch den Container zu tingeln... wie kommst du auf O(N log N)?
-
Konkret hat der OP vor das Minimum zu bestimmen. Ein Baum ist ergo nicht sinnvoll.
Zum zweiten ne kleine gegenfrage: in welcher Laufzeit möchtest Du den Suchbaum aufbauen? O(N)?
Bedenke: Ist der Suchbaum schon aufgebaut, so kann man ihn in-order traversieren und so ne sortierte Folge rauslassen und zwar in O(N) Laufzeit. Da wir aber alle wissen (tun wir das?), daß Sortieren O(N log N) Vergleichsoperationen benötigt muß das Aufbauen des Baums schonmal mindestens O(N log N) Laufzeit benötigen.Ich bin dennoch auf Deine Analyse für die Laufzeit beim Aufbau des Baums gespannt.
Natürlich ist es schneller wenn man den Suchbaum schon hat. Nur den aufzubauen ist langsamer als 2mal durchzutingeln.
edit: um euren Lösungsvorschlag mal konkret zu implementieren. Ihr sagt: hau alles in ne std::map rein und nimm dann *myMap.begin(); Und das wollt ihr uns nun als tolle Lösung für das Problem verkaufen? Wenn ihr das vorher noch schön in ne Funktion packt schick ich's direkt bei thedailywtf.com ein.
-
Jester schrieb:
Konkret hat der OP vor das Minimum zu bestimmen. Ein Baum ist ergo nicht sinnvoll.
Zum zweiten ne kleine gegenfrage: in welcher Laufzeit möchtest Du den Suchbaum aufbauen? O(N)?
Bedenke: Ist der Suchbaum schon aufgebaut, so kann man ihn in-order traversieren und so ne sortierte Folge rauslassen und zwar in O(N) Laufzeit. Da wir aber alle wissen (tun wir das?), daß Sortieren O(N log N) Vergleichsoperationen benötigt muß das Aufbauen des Baums schonmal mindestens O(N log N) Laufzeit benötigen.Ich bin dennoch auf Deine Analyse für die Laufzeit beim Aufbau des Baums gespannt.
Natürlich ist es schneller wenn man den Suchbaum schon hat. Nur den aufzubauen ist langsamer als 2mal durchzutingeln.
edit: um euren Lösungsvorschlag mal konkret zu implementieren. Ihr sagt: hau alles in ne std::map rein und nimm dann *myMap.begin(); Und das wollt ihr uns nun als tolle Lösung für das Problem verkaufen? Wenn ihr das vorher noch schön in ne Funktion packt schick ich's direkt bei thedailywtf.com ein.
Ja da hast du Recht, ich habe dich ein wenig missverstanden.
-
Natürlich ist es Schwachsinn den Baum jedesmal neu aufzubauen.
Aber abhängig davon "was der OP konkret vorhat", (womit ich meinte was sind das für Werte?, wie sieht die Benutzungscharakteristik aus?,) kann es durchaus Sinn machen entweder direkt ein set als Container zu nehmen oder eine View darauf anzulegen.
-
Was wird denn hier schon wieder gezankt? Der OP hat nichtmal leise angedeutet dass er ne schnelle oder sonstwie spezielle Lösung haben will. Ok, das dummes O(N) Kommentar welches hier anscheinend einen Krieg ausgelöst hat stammt von mir, sorry. Ich sehe halt nicht ganz ein wieso man jmd. der offensichtlich nicht so DEN Plan hat mit Bäumen zulabern muss wovon er mit grosser Wahrscheinlichkeit nix verstehen wird -- wenn nichtmal offensichtlich ist dass es bei seinem Problem von Vorteil wäre einen Baum zu verwenden. Trotzdem, das muss nicht so ausarten. Ich denke wir wissen alle dass Bäume Sinn machen können und inetwa wann und wo sie Sinn machen können und wann/wo nicht.
Also ja, ein Baum ist eine Lösung die definitiv funktioniert. Die einfache Suche genauso. Die ganze Liste mit bubblesort/quicksort/... zu sortieren wäre auch eine Lösung die definitiv funktioniert. Was nu am besten geeignet ist kann nur der OP wissen da nur er sein spezielles Problem kennt.
-
finix schrieb:
Natürlich ist es Schwachsinn den Baum jedesmal neu aufzubauen.
Es ist auch langsamer, wenn Du ihn nur einmal aufbaust. Zumindest nur wenn man das Minimum haben will.
@Plotzenhotz: Ich finde es wichtig hier klarzustellen, daß der Ansatz mit Bäumen für eine einfache Minimumsuche quatsch ist. Der nächste liest das sonst hier und denkt es sei besonders schnell. Es geht nicht nur darum was funktioniert (so lange zufällig ziehen, bis selbst nach 1000 Ziehungen kein kleineres Element mehr gekommen ist funktioniert auch mehr oder weniger). Trotzdem ist es für die meisten Anwendungen keine gute Lösung.
-
Jester schrieb:
finix schrieb:
Natürlich ist es Schwachsinn den Baum jedesmal neu aufzubauen.
Es ist auch langsamer, wenn Du ihn nur einmal aufbaust. Zumindest nur wenn man das Minimum haben will.
Dir ist klar dass zumindest ich von einem Suchbaum geredet habe, ja?
-
@Jester: ja, im Grunde genommen stimme ich ja mit dir überein. Und gerade weil die Frage bloss "min. Element finden" ohne nähere Info war hätte ich mal den einfachsten Algorithmus vorgeschlagen, der nunmal ne einfache Suche ist.
Und weil wir schon bei möglichen Lösungen sind die vll. sogar manchmal Sinn machen (oder auch nicht): man nehme eine Datenbank (z.B. sqlite), stecke die Werte in einen Table, und selektiere sich den kleinsten Wert raus
@fixnix: du kannst auch einen Suchbaum nicht in O(N) aufbauen. Wie gesagt, wenn man viele min/max Abfragen drauf macht (mit Änderungen dazwischen, sonst könnte man den Wert/die Werte ja einfach cachen) und/oder mehrmals eine (Teil-)Folge sortiert durchgehen will ist ein Baum sicher die beste Wahl.
-
Plotzenhotz schrieb:
@fixnix: du kannst auch einen Suchbaum nicht in O(N) aufbauen. Wie gesagt, wenn man viele min/max Abfragen drauf macht (mit Änderungen dazwischen, sonst könnte man den Wert/die Werte ja einfach cachen) und/oder mehrmals eine (Teil-)Folge sortiert durchgehen will ist ein Baum sicher die beste Wahl.
Deine schwachsinnige Nickänderung wirkt eher kindisch als irgendetwas sonst.
Und wenn du drei, vier Posts hochscrollst wirst du sehen dass ich gar nicht behauptet einen Suchbaum in O(N) aufbauen zu können. (Ich traue dir durchaus zu das aus meiner Aussage ableiten zu können.)
Ich habe lediglich angemerkt dass je nach dem wie des OPs konkreter Anwendungsfall aussieht es entweder sinnvoll ist die Menge georndet zu speichern oder dass ggf. eine View darauf ein lohnenswerter Trade-Off sein könnte.
Im Prinzip also ähnlich dem was du vorschlägst.
Du scheinst also nicht wirklich "DEN Plan" vom Lesen zu haben.
-
@finix:
lol. Koffer.
-
Plotzenhotz schrieb:
@Jester: ja, im Grunde genommen stimme ich ja mit dir überein. Und gerade weil die Frage bloss "min. Element finden" ohne nähere Info war hätte ich mal den einfachsten Algorithmus vorgeschlagen, der nunmal ne einfache Suche ist.
Und weil wir schon bei möglichen Lösungen sind die vll. sogar manchmal Sinn machen (oder auch nicht): man nehme eine Datenbank (z.B. sqlite), stecke die Werte in einen Table, und selektiere sich den kleinsten Wert raus
@fixnix: du kannst auch einen Suchbaum nicht in O(N) aufbauen. Wie gesagt, wenn man viele min/max Abfragen drauf macht (mit Änderungen dazwischen, sonst könnte man den Wert/die Werte ja einfach cachen) und/oder mehrmals eine (Teil-)Folge sortiert durchgehen will ist ein Baum sicher die beste Wahl.
Hallo, ich hab doch schon Jester Recht gegeben (wird Recht hier überhaupt groß geschrieben).
Wollt ja blos sagen das wenn man doch etwas sortiert haben will, ein Baum Sinn macht.
------
Baum Aufbauen: O(nlog n)
danach O(1)
------
Einmal Suchen O(n)
Zweites mal Suchen O(n)
usw.
Ergibt insgesammt O(n²)
-
O(n^2) aber nur, wenn auch wirklich n Suchanfragen da sind. Ist es ne konstante Anzahl k, dann O(n*k) = O(n) wegen k Konstante. Klar, hat man viele Anfragen, dann sollte man nicht jedes Mal komplett durchlaufen. Mein Lösungsfavorit dafür wäre allerdings ne sortierte Liste, sofern die Datenstruktur nicht dynamisch sein muß. Nur wenn das auch noch gefordert ist (man also die Werte über die das Minimum etc gesucht wird sich ändern), ist der Baum ne wirklich gute Lösung.
@finix: klar, ein Suchbaum. Sonst könnteste den beliebigen Baum ja in O(N) aufbauen, aber Suchen wäre nicht effizient.
-
finix schrieb:
Benutzungscharakteristik
aua.
-
DEvent schrieb:
Wollt ja blos sagen das wenn man doch etwas sortiert haben will, ein Baum Sinn macht.
na, dann halt DEvent-bashing, die 2. runde.
wenn man etwas sortiert haben will, nimmt man eine sortierfunktion. das ist sinnvoll. nur ganz selten ist ein baum sinnvoll. zum beispiel dann, wenn man es jederzeit sortiert habern will, um auch bereits in der einfüllphase schnelle suchzugriffe haben will UND wenn man nicht nur immer den kleinsten (die k kleinsten) oder größten braucht.