1) Le pire des cas d'insertion d'un élément dans une liste linéaire contenant n éléments.Complexité du hachage (pire des cas)
2) Le pire des cas d'insertion d'un élément dans une table de hachage avec n éléments et b emplacements, où chaque emplacement est une chaîne triée (certains emplacements peuvent être vides).
Je pense que (1) est O (n) mais je n'ai aucune idée de ce que (2) est.
Le pire cas de (2) est aussi O (n). C'est parce que tous les n éléments (ou au moins une bonne partie d'entre eux) dans le hachage (de très très mauvaise chance) pourraient se retrouver dans un emplacement spécifique, et aussi ce nouvel élément est mappé à nouveau à cette salope. Le nouvel élément doit donc être inséré dans une liste triée de taille n, qui doit être décalée d'un autre élément, et sera par conséquent O (n).
Cependant, dans le hachage, les gens sont généralement préoccupés par le comportement moyen plutôt que par le pire des cas.
Merci beaucoup. –
@SaminKhan Pas de problème. Si vous pensez que cette réponse est satisfaisante, veuillez l'accepter comme meilleure réponse. –
Faites-vous référence à un code lorsque vous essayez de trouver ces complexités de temps? Cela peut vous aider grandement à comprendre ce que c'est et pourquoi. – 4castle
Je vous suggère de faire d'abord des recherches, afin de pouvoir poser une question de qualité supérieure. – 4castle
L'insertion dans une table de hachage est un O (1) moyen. Dans le pire des cas, chaque valeur de la table entre en collision avec la même valeur de hachage, de sorte que le temps d'insertion devient le même que pour une chaîne triée, car tous les éléments se trouvent dans le même intervalle. – 4castle