1
Quelle structure de données prend en charge efficacement les opérations d'ensemble suivantes dans le temps et dans l'espace?Structure de données pour les opérations d'ensemble
- union
- différence
- isMemberOf
- ajouter
- supprimer
Je peux penser à 3 façons différentes de faire ces opérations, supposons que nous avons deux ensembles, leurs tailles sont les deux N:
Bit Tableau:
1. O(N) 2.O(N) 3.O(1) 4.O(1) 5.O(1)
Hashtable:
1. O(N) 2.O(N) 3.O(1) 4.O(1) 5.O(1)
Ordonné Arbre:
1. O(NlogN) 2.O(NlogN) 3.O(logN) 4.O(logN) 5.O(logN)
Bit tableau et Hashtable sont rapides mais ils utilisent trop de mémoire, arbre ordonné est lent mais consomme moins de mémoire.
S'il vous plaît noter: l'ensemble peut contenir d'autres types sauf entier, tels que le nombre flottant ou une chaîne
Quelles sont les autres structures de données sont à la fois rapide et générale, et efficace de l'espace?
Quelle est l'application dans laquelle vous essayez d'utiliser cette structure de données? –
Pourquoi ne peut pas une table de hachage (jeu de hachage) tenir arbitraire (mais comparable) des objets comme un arbre ordonné? –
Pour l'analyse du journal, toutes les opérations ne sont pas nécessaires, mais je suis curieux. – outlaw