Régler l'heure et la vitesse de la complexité

Je suis brosser les algorithmes et structures de données et avoir quelques questions ainsi que des déclarations je voudrais que vous le vérifier.

ArrayList - O(1) (taille, get, set, ...), O(n) - opération d'ajout.
LinkedList - toute opération O(1) (y compris les ajouter() ), sauf pour la récupération du n-ième élément qui est O(n). Je suppose size() opération s'exécute en O(1) ainsi, le droit?

TreeSet - toutes les opérations en O(lg N)). size() prend O(lg(n)), à droite?

HashSet - toutes les opérations en O(1) si la fonction de hachage est appliquée.
HashMap - toutes les opérations en O(1), anologous à HashSet.

Toutes explications sont très bienvenue. Je vous remercie à l'avance.

Si vous avez une telle magie HashSet, pourquoi avez-vous besoin d'ArrayList?
Parce que une Liste et un Ensemble ne sont pas la même chose, et aussi parce que la constante de facteurs peuvent encore être sensiblement différente...
La commande ne vous donne une idée de la façon dont l'opération échelles. Il ne vous dira pas le facteur par exemple HashSet peut être plusieurs fois plus lente que la liste de tableaux et de ne pas "get ()" /méthodes set ().
Lawrey, @Jon Skeet Vous avez raison. C'est pourquoi je pense que ces la compassion est trompeuse.
ils sont seulement trompeuse si vous ne comprenez pas grand-O notation. Je ne vois aucune preuve de ce que quelqu'un ici soit induit en erreur ou de confusion.

OriginalL'auteur Anton K. | 2011-07-09