Régler la complexité du temps et de la vitesse

Question

Je brosse des algorithmes et des structures de données et j'ai quelques questions ainsi que des affirmations que je voudrais que vous vérifiiez.

ArrayList - O (1) (taille, obtenir, définir, ...), O (n) - ajouter une opération.
LinkedList - toute l'opération O (1) (y compris add()), sauf pour récupérer le nième élément qui est O (n). Je suppose que l'opération size() s'exécute également dans O (1), non?

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), anologous à HashSet.

Toute autre explication est la bienvenue. Merci d'avance.

Answer 1

ArrayList.add() est amorti O (1). Si l'opération ne nécessite pas de redimensionnement, c'est O (1). Si nécessite un redimensionnement, c'est O (n), mais la taille est alors augmentée de sorte que le prochain redimensionnement ne se produira pas pendant un certain temps.

De l'Javadoc:

L'opération d'ajout fonctionne en temps constant amorti, à savoir, l'ajout d'éléments n nécessite O (n). Toutes les autres opérations s'exécutent en temps linéaire (grosso modo). Le facteur constant est faible par rapport à celui de l'implémentation LinkedList.

La documentation est généralement très bonne pour les collections Java, en termes d'analyse des performances. Le O (1) pour les algorithmes de hachage ne consiste pas simplement à appliquer une fonction de hachage "correcte" - même avec une très bonne fonction de hachage, vous pourriez toujours avoir des collisions de hachage. La habituelle complexité est O (1), mais bien sûr, il peut être O (n) si tous les les hachages arrivent à entrer en collision.

Answer 2

Visitez les liens suivants. Cela vous aidera à clarifier vos doutes.

• Data structures & their complexity
• Java standard data structures Big O notation