Kann mir jemand Referenzen einer Website geben, die eine Zusammenfassung der wichtigsten Java-Datenstrukturen und ihre jeweilige Komplexität in der Zeit (für einige Operationen wie hinzufügen, finden, entfernen), z. Hashtable s sind O (1) zum Auffinden, während LinkedList s O (n) sind. Einige Details wie Speicherverbrauch wären auch nett.Java Data Structures Referenz
Dies wäre sehr hilfreich für das Denken in Datenstrukturen für Algorithmen.
Gibt es einen Grund zu glauben, dass Java-Implementierung unterscheidet (im Hinblick auf die Komplexität) als eine allgemeine, sprachunabhängig Implementierung? Mit anderen Worten, beziehen sich, warum nicht nur auf einen allgemeinen Verweis auf die Komplexität der verschiedenen Datenstrukturen:
NIST Dictionary of Algorithms and Data Structures
Aber, wenn Sie auf Java-spezifische bestehen:
Java standard data structures Big O notation
Java Collections cheatsheet V2 (toter Link, aber this is the first version of the cheatsheet)
Ich glaube nicht, dass es eine einzelne Website gibt, die dies umreißt (klingt aber nach einer guten Idee für ein Projekt). Ich denke, ein Teil des Problems besteht darin, dass ein Verständnis dafür, wie jeder der Algorithmen läuft, sehr wichtig ist. Zum größten Teil klingt es so, als ob du Big-O verstehst, also würde ich das als deine besten Vermutungen benutzen. Wiederholen Sie dies mit einem Benchmarking/Profiling, um zu sehen, was schneller/langsamer läuft.
Und ja, die Java docs sollte viel von dieser Information in java.util haben.
Die umfassendste Java Collections Übersicht ist hier
+1 für die Wikiversity-Seite –
Ich fand sehr nützlich The Collections Framework Seite, vor allem die Outline of the Collections Framework, wo jede Schnittstelle/Klasse Breeefly beschrieben wird. Leider gibt es keine Big-O-Informationen.
Ich konnte diese besondere Ressource hier nicht erwähnt sehen, ich habe es in der Vergangenheit als sehr nützlich empfunden. Kenne deine Komplexität!
Anders als die Javadocs? –
Ja, Java Docs haben sie alle getrennt, und Komplexität ist nicht wirklich leicht zu finden. Ich will keine Details von jedem, nur eine Zusammenfassung mit Zeitkomplexitäten –