die Komplexität von set::insert

Habe ich gelesen, dass die insert-operation in ein set dauert nur log(n) Zeit. Wie ist das möglich?

Einfügen, zuerst haben wir die Position im sortierten array, wo das neue element muss sitzen. Unter Verwendung der binären Suche, dauert es log(n). Dann einfügen in, der Lage, alle Elemente gelingt es verschoben werden soll um eine Stelle nach rechts. Es dauert noch n Zeit.

Meine Frage ist nach meinem Verständnis dieses Satzes ist implementiert als array und die Elemente werden gespeichert in sortierter Reihenfolge. Bitte korrigieren Sie mich, wenn mein Verständnis falsch ist.

  • Sie sind unter der Annahme, dass std::set ist implementiert als ein sortiertes array. Warum?
  • Entnommen aus cppreference: die Sätze sind in der Regel umgesetzt als rot-schwarz-Bäume.
  • Jetzt erst habe ich erfahren, dass sets sind implementiert mit rot-schwarz-Baum. Dank chris
  • Gut, es sollte bekannt sein, wer die Sorge um Daten-Strukturen, die sets sind in der Regel umgesetzt mit - Bäume oder hashes, nicht mit arrays, wegen der Leistung... was Solls, in Java haben, haben Sie eigentlich, um zu entscheiden, ob Sie eine HashSet oder eine TreeSet (das ist ein SortedSet), und ich bezweifle, dass es eine ArraySet zur Verfügung. (Beachten Sie, dass die unmodifiable-sets können effizient implementiert werden als ein array sortiert, mit binarysearch-Methode - also eigentlich wie einen Baum sortiert, gespeichert in einem array)
  • Eigentlich eine flat set ist in vielen Fällen schneller, als ein Baum-basierter set, aufgrund von cache-Lokalität.
  • Accoriding zu cplusplus.com Komplexität ist logN. Wenn Sie angeben, die position ist, amortisiert Konstante ist, und zum einfügen von n Elementen - n.log (set_size + n)
  • Ich kann kompilieren meinen Satz in einen endlichen Automaten (man denke an den regulären Ausdrücken), an welchem Punkt wird es zu übertreffen, um eine flache Liste. Aber es ist auch weniger allgemein. Haben Sie einmal größere Mengen als Ihre cache-Größe, - Baum und hash-sets gewinnen, wenn gut umgesetzt. Der Punkt ist, die Chancen der Baum/hash-set der Durchführung wirklich schlimm, einen niedrigen. Eine Wohnung kann gut - oder wirklich langsam.

InformationsquelleAutor bibbsey | 2012-10-08
Schreibe einen Kommentar