Ich aktualisiere Algorithmen und Datenstrukturen und habe ein paar Fragen sowie Aussagen, die ich gerne überprüfen würde.
ArrayList - O (1) (size, get, set, ...), O (n) - Operation hinzufügen.
LinkedList - Alle Operationen O (1) (einschließlich add ()), außer zum Abrufen des n-ten Elements, das O (n) ist. Ich nehme an, die Operation size () läuft auch in O (1), oder?
TreeSet - alle Operationen O (lg (N)). Die Operation size () benötigt O (lg (n)), richtig?
HashSet - alle Operationen O (1), wenn die richtige Hash-Funktion angewendet wird.
HashMap - alle Operationen O (1), die zu HashSet gehören.
Weitere Erklärungen sind sehr willkommen. Vielen Dank im Voraus.
ArrayList.add() ist amortisiert O (1). Wenn der Vorgang keine Größenänderung erfordert, ist O (1). Wenn eine Größenänderung erfordert, ist es O (n), aber die Größe wird dann so erhöht, dass die nächste Größenänderung für eine Weile nicht mehr auftritt.
Aus dem Javadoc :
Die Additionsoperation wird in der amortisierten konstanten Zeit ausgeführt, dh das Hinzufügen von n Elementen erfordert O (n) Zeit. Alle anderen Operationen laufen (grob gesagt) linear ab. Der konstante Faktor ist im Vergleich zu dem der LinkedList-Implementierung gering.
Die Dokumentation ist in Bezug auf die Performance-Analyse im Allgemeinen ziemlich gut für Java-Sammlungen.
Beim O (1) für Hashalgorithmen geht es nicht darum, nur eine "richtige" Hash-Funktion anzuwenden - selbst mit einer sehr guten Hash-Funktion könnten Sie immer noch Hash-Kollisionen bekommen. Die übliche Komplexität ist O (1), aber natürlich kann sie O (n) sein, wenn alle die Hashes zufällig kollidieren.
(Darüber hinaus werden die Kosten für das Hashing als O (1) gezählt - in Wirklichkeit, wenn Sie beispielsweise Strings hashen, kann jeder Aufruf von hashCode in der Länge des Strings O (k) sein.)
Besuchen Sie die folgenden Links. Es wird dir helfen, deine Zweifel auszuräumen.
Tags und Links algorithm java collections