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.
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
Vous devez vous connecter pour publier un commentaire.
ArrayList.add()
est amorti O(1). Si l'opération ne nécessite pas de redimensionnement, il est O(1). Si il ne besoin d'un redimensionnement, c'est O(n), mais la taille est alors augmentée telle que la prochaine redimensionner de ne pas se produire pendant un certain temps.De la Javadoc:
La documentation est généralement assez bon pour Java collections, en termes d'analyse de la performance.
Le O(1) pour les algorithmes de hachage n'est pas une question de se contenter d'appliquer une "bonne" fonction de hachage - même avec une très bonne fonction de hachage, vous pourrait encore se produire pour obtenir des collisions de hachage. Le d'habitude la complexité est O(1), mais il peut bien sûr être O(n) si tous les hachages arriver à entrer en collision.
(En plus, c'est compter le coût de hachage O(1) en réalité, si vous êtes chaînes de hachage par exemple, chaque appel à
hashCode
peut être O(k) de la longueur de la chaîne)."il ne déclenche pas une table"?
GC = "garbage collection" (?)
LinkedList.ajouter() crée toujours un objet et il consomme plus de mémoire que la liste de tableaux. Alors que sur le papier ArrayList aura des retards LinkedList n'a pas, c'est plus moins susceptibles de provoquer certains retards les plus importants de tous.
Des commentaires à ce sujet?
OriginalL'auteur Jon Skeet
Visiter les liens suivants. Il vous aidera à obtenir vos doutes effacés.
OriginalL'auteur sgokhales