Je suis en train de brosser des algorithmes et des structures de données et j’ai quelques questions ainsi que des déclarations que je voudrais que vous vérifiiez.
ArrayList – O (1) (taille, get, set, …), O (n) – opération add.
LinkedList – toute l’opération O (1) (y compris add ()), sauf pour récupérer le n-ième élément qui est O (n). Je suppose que l’opération size () s’exécute également dans O (1), n’est-ce pas?
TreeSet – toutes les opérations O (lg (N)). L’opération size () prend O (lg (n)), n’est-ce pas?
HashSet – toutes les opérations O (1) si la fonction de hachage appropriée est appliquée.
HashMap – toutes les opérations O (1), analogues à HashSet.
Toute autre explication est la bienvenue. Merci d’avance.
ArrayList.add()
est amorti sur O (1). Si l’opération ne nécessite pas de redimensionnement, c’est O (1). Si cela nécessite un redimensionnement, c’est O (n), mais la taille est ensuite augmentée pour que le prochain redimensionnement ne se produise pas pendant un certain temps.
De la Javadoc :
L’opération add s’exécute en temps constant amorti, c’est-à-dire que l’ajout de n éléments nécessite un temps O (n). Toutes les autres opérations se déroulent en temps linéaire (en gros). Le facteur constant est faible par rapport à celui de l’implémentation de LinkedList.
La documentation est généralement assez bonne pour les collections Java, en termes d’parsing de performance.
Le O (1) pour les algorithmes de hachage ne consiste pas simplement à appliquer une “bonne” fonction de hachage – même avec une très bonne fonction de hachage, il peut arriver que des collisions de hachage se produisent. La complexité habituelle est O (1), mais bien sûr, il peut s’agir de O (n) si tous les hashs entrent en collision.
(De plus, le coût de hachage est calculé en tant que O (1) – en réalité, si vous hachez des chaînes, par exemple, chaque appel à hashCode
peut avoir la longueur O (k) dans la chaîne.)
Visitez les liens suivants. Cela vous aidera à dissiper vos doutes.