Quel est le Meilleur et le Pire//Moyenne des Cas Big-O de l'Exécution d'un Trie de la Structure de Données?

Quel est le meilleur et le pire//moyenne de la complexité de l'affaire (en Big-O notation) d'un trie de la structure de données pour l'insertion et la recherche?

Je pense que c'est O(K) pour tous les cas, où K est la longueur d'une chaîne de caractères arbitraire qui est en cours d'insertion ou de recherche. Quelqu'un confirmer?

OriginalL'auteur Karim Elsheikh | 2013-07-26

  1. 15

    Selon Wikipédia et cette source, le pire des cas, la complexité pour l'insertion et la recherche d'un trie est O(M) où M est la longueur de la clé. Je ne suis pas à trouver toutes les sources décrivant le meilleur de moyen ou de la complexité de l'insertion et de la recherche. Cependant, nous pouvons dire que le mieux et de la moyenne de la complexité de l'affaire est O(M) où M est la longueur de la clé, depuis le Big-O ne décrit que la limite supérieure de la complexité.

    OriginalL'auteur Alex Brooks

  2. 5

    k: la longueur de la chaîne que vous recherchez ou insérer.

    For Search

Worst: O(26*k) = O(k)
Average: O(k)          # In this case, k is an average length of the string
Best: O(1)             # Your string is just 'a'.

    Trie de la complexité ne change pas avec le nombre de chaînes que vous recherchez, qu'avec la recherche de la chaîne de longueur. C'est pourquoi Trie est utilisé lorsque le nombre de chaînes de recherche est grande, comme la recherche de l'ensemble du vocabulaire dans un dictionnaire d'anglais.

    For Insertion

Worst: O(26*k) = O(k)
Average: O(k) 
Best: O(1)

    Donc, oui, vous avez raison. Vous avez probablement vu O(MN) et qui ont pu confondre, mais il est tout simplement parler de ce que vous devez faire au-dessus de O(k) opérations de N fois.

    OriginalL'auteur Aerin

  3. 0

    Il y a quelques info à ce sujet sur Wikpedia. http://en.wikipedia.org/wiki/Trie

    OriginalL'auteur Ralph Caraveo