Zeitkomplexität verschiedener Sammlungen in Java

-1

In den meisten Fällen der konkurrierenden Programmierung ist es notwendig, vor der Verwendung die Komplexität eines Codes zu kennen. Wir verwenden verschiedene Bibliotheksfunktionen und STL in C++ - Codierung. Und es gibt eine schöne Dokumentation über STL mit Komplexitäten.Zeitkomplexität verschiedener Sammlungen in Java

Ich möchte über die Komplexität der verschiedenen integrierten generischen Collections-Methoden (z. B. Komplexität von java.util.Arrays.sort()) in Java wissen. Gibt es überhaupt eine angemessene Dokumentation über die Komplexität in Java?

Vielen Dank im Voraus.

Quelle

2017-01-13 Shikhor Roy

Versuchten Sie auch die [Dokumentation] zu lesen (https://docs.oracle.com/javase/8/ docs/api /)? Es ist alles drin, einschließlich Anmerkungen zur Implementierung und Komplexität. – Axel

Die "schöne Dokumentation", die Sie erwähnt haben, ist hier in der Regel verpönt. Sie sind besser dran mit cppreference.com. Siehe http://stackoverflow.com/questions/6520052/whats-wrong-with-cplusplus-com. Es ist auch nicht die "STL", wohlgemerkt. Siehe http://stackoverflow.com/a/5205571/3313064 –

Was ich eigentlich wissen möchte, ist die Komplexität nicht nur die Methoden Dokumentationen. Lassen Sie mich ein Beispiel geben, [link] (https://docs.oracle.com/javase/8/docs/api/) zeigt die Dokumentation von HashMap. Lassen Sie eine Methode wählen "bekommen", der Artikel zeigt mir, wie funktioniert es (Methode erhalten) arbeiten ... aber wo ist die Komplexität der "Get" -Methode? Gibt es mir die Elemente in O (1) Komplexität oder O (n)? @Axel –

Bitte lesen offizielle Oracle-Dokumentation mit Aufmerksamkeit, zum Beispiel zitieren aus (https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#sort(byte[])) -

Umsetzung beachten Sie: Der Sortieralgorithmus ist ein Dual-Pivot Quicksort von Vladimir Yaroslavskiy, Jon Bentley, und Joshua Bloch. Dieser Algorithmus bietet O (n log (n)) - Leistung für viele Datensätze, die andere Quicksorts zu einer quadratischen Leistung führen, und ist in der Regel schneller als herkömmliche (ein Pivot) Quicksort-Implementierungen.

Wie Sie O (n log (n)) wird sehen

angegeben

Quelle

2017-01-13 10:21:44 Dewfy

Aber jedes Mal kann ich die Komplexität nicht bekommen. z. B. https://docs.oracle.com/javase/7/docs/api/java/util/Map.Entry.html#getKey(), keine Komplexität für die Methode getValue() !!! –

@ShikhorRoy es ist, weil 'getValue()' keinen Algorithmus implementiert - es ist nur Accessor zu zugrunde liegenden Daten – Dewfy

@ShikhorRoy selbst wenn die Zeit Komplexität nicht angegeben ist, ist es leicht herauszufinden, was ist die Zeit Komplexität für eine bestimmte Methode. ZB verwendet java [Timsot] (https://en.wikipedia.org/wiki/Timsort) für den Sortierungsalgorithmus von Arraylisten. –

Zeitkomplexität verschiedener Sammlungen in Java

Antwort

Verwandte Themen