Définir le temps et la complexité

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.

  • Structures de données et leur complexité
  • Structures de données standard Java Big O notation