2
Quelle est la durée de fonctionnement (grand Oh) pour un sondage linéaire sur l'insertion, la suppression et la recherche.Temps d'exécution pour le sondage linéaire sur table de hachage
Merci
A
Répondre
3
théorique pire des cas est O (n) car si vous arrive d'insérer tous les éléments tels qu'ils entrent en collision consécutivement alors le dernier élément inséré devra être mis dans la table n étapes de son hachage d'origine position.
Vous pouvez cependant calculer le nombre moyen attendu d'étapes si vous connaissez la distribution de vos éléments d'entrée (en supposant que le hasard, mais bien sûr l'hypothèse est la mère ...), connaître la distribution de votre fonction de hachage , mais cela dépend de la qualité de votre algorithme), de la longueur de votre table de hachage et du nombre d'éléments insérés. Si votre fonction de hachage est suffisamment uniforme, vous pouvez calculer la probabilité de collisions en utilisant le problème d'anniversaire et, à partir de ces probabilités, calculer les longueurs de sondage attendues.
Etes-vous sûr? Que faire si vous avez une collision à chaque insertion? Ensuite, vous devrez sauter 1 slot, puis 2, puis 3, .... alors n. Vous auriez 1 + 2 + 3 + ... n qui vous donne une complexité de O (n^2>, n'est-ce pas? – CodyBugstein
C'est ce que j'ai dit, la complexité pour le sondage linéaire est O (n) ce qui signifie O (n) pour * chaque * insertion/suppression/recherche Donc, si vous avez n insertions alors votre complexité totale est O (n^2) – wich