2014-03-03 8 views
6

Ich versuche herauszufinden, die Komplexität des Löschens mehrerer Elemente von Std :: Set. Ich verwende this page als Quelle.std :: set löschen komplexität anomalität?

Es behauptet, dass die Komplexität für das Löschen eines einzelnen Elements mit einem Iterator amortisiert O (1), aber das Löschen mehrerer Elemente mit der Bereichsform ist log (c.size()) + Std :: distance (erste, letzte) (dh - Protokoll der Größe des Sets + Anzahl der gelöschten Elemente).

Wenn die Anzahl der zu löschenden Elemente (n) viel kleiner ist als die Anzahl der Elemente in der Menge (m), bedeutet dies, dass die Elemente, die gelöscht werden sollen, wiederholt und gelöscht werden eine Zeit ist schneller (O (n)) als sie mit einem Aufruf zu löschen (O (log m) unter der Annahme n < < m).

Offensichtlich, wenn das wirklich der Fall gewesen wäre, würde die interne Implementierung der zweiten Form nur die obige Schleife tun.

Ist dies ein Fehler auf der Website? Ein Fehler in den Spezifikationen? Fehle ich gerade etwas?

Danke, Shachar

+3

mehrere Artikel mit dem Bereich Form _erasing ist log (c.size()) + std :: Abstand (first, last) (dh - Protokoll der Größe des Satzes + die Anzahl der Elemente gelöscht). _ - mit fester Satzgröße ist genau wie O (n) skaliert, wobei n die Anzahl der gelöschten Elemente ist, die man erhält, wenn man sie einzeln löscht. – Cthulhu

+0

Das ist interessant, ich denke, Sie könnten es beide Möglichkeiten testen, um den Unterschied zu sehen. Vielleicht würde es beim Zurücksetzen des Iterators nach jedem einzelnen Löschen etwas Overhead geben (da dies den Iterator ungültig macht) –

+1

@Cthulhu, die gleiche Logik gilt immer dann, wenn ein Plus in der Komplexität verwendet wird. Alles, was Sie für konstant halten (oder sogar beschränkt), hat automatisch die Komplexität von O (1). –

Antwort

1

Es scheint, das Problem hinter dem (etwas Wiesel) Wort "abgeschrieben" versteckt. Das Löschen einzelner Elemente hat eine O-Komplexität von log (c.size()), aber amortisierte Komplexität von O (1).

Das Ausführen mehrerer einzelner Löschungen in einer Schleife kostet also log (c.size()) + Anzahl der Löschungen, was genau der Komplexität der Bereichsform entspricht.

Shachar

+4

"Amortized" ist kein Wieselwort. Es ist ein gut etablierter Begriff aus der Informatik: http://en.wikipedia.org/wiki/Amortized_analysis. –

+0

Okay, "Wiesel" ist ein bisschen hart. Ich denke, dass das Ablegen der strikten Obergrenze der Aussage Verwirrung stiftet. Wenn Sie nur die amortisierte Komplexität einer Operation bereitstellen, entziehen Sie einem Programmierer oft die Fähigkeit zu wissen, was zu erwarten ist. Ich stimme zu, dass die Verwendung nur der O-Komplexität kann ebenso irreführend sein (wie hier), aber ich denke, der Standard sollte beide erwähnt haben. –