Quelle mémoire supplémentaire une solution avec dictionnaire nécessite-t-elle, sans compter les données retournées?

L'utilisation d'un dictionnaire (table de hachage) nécessite une mémoire supplémentaire proportionnelle au nombre de clés uniques qui y sont ajoutées. Si vous avez N éléments uniques, la mémoire sera d'environ O(N), car de l'espace est alloué pour chaque clé et sa valeur associée.

Par exemple, si vous créez un dictionnaire pour compter le nombre d'occurrences de mots dans un texte, la mémoire augmentera avec le nombre de mots uniques. La structure du dictionnaire comprend généralement des coûts supplémentaires pour le stockage des valeurs de hachage et la gestion des collisions, mais en général, l'estimation de O(N) en mémoire supplémentaire est la plus pratique.