La complexité algorithmique de TreeSet opérations en Java?

Je suis en train d'essayer d'éclaircir certaines choses au sujet de la complexité de certaines opérations de TreeSet. Sur la javadoc, il dit:

"Cette application fournit
garanti log(n) coût du temps pour les
les opérations de base (ajouter, supprimer et
contient)."

So far So good. Ma question est de savoir ce qui se passe sur addAll(), removeAll (), etc. Ici la javadoc pour Définir dit:

"Si la collection est également un
ensemble, les addAll fonctionnement efficace
modifie cette série, de sorte que sa valeur est
l'union des deux ensembles."

Est-il juste d'expliquer le résultat logique de l'opération ou est-il en donnant une indication sur la complexité? Je veux dire, si les deux ensembles sont représentés par exemple par les arbres rouge-noir, il serait mieux de faire en quelque sorte rejoindre les arbres qu'à "ajouter" chaque élément de l'un à l'autre.

Dans tous les cas, il est un moyen de combiner les deux TreeSets en un avec O(logn) de la complexité?

Vous en remercie d'avance. 🙂

Réponse à la réponse j'ai eu: je ne comprends pas très bien cette. Supposons que vous avez deux SortedSets qui n'ont pas d'-les éléments qui se chevauchent et qui sont représentés par des arbres rouge-noir. Comment se fait que vous ne pouvez pas vous joindre à eux depuis le "rejoindre" l'opération dans les arbres rouge-noir prendre en O(log(n+m)) de temps?

OriginalL'auteur Andreas K. | 2010-08-02

7

Vous pouvez imaginer comment il serait possible d'optimiser les cas spéciaux O(log n), mais le pire des cas a obtenu d'être O(m log n) où m et n sont le nombre d'éléments dans chaque arbre.

Edit:

http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm

Décrit un cas particulier de l'algorithme qui peut joindre les arbres dans O(log(m + n)) mais note la restriction: tous les membres de S1 doit être inférieur à tous les membres de S2. C'est ce que je voulais dire qu'il y a des optimisations spéciales pour les cas particuliers.

Lien dans la réponse semble mort...

OriginalL'auteur bshields
3

En regardant le source java pour TreeSet, il semble comme si le passé dans la collection est un SortedSet ensuite, il utilise un O(n) en temps de l'algorithme. Sinon, il appelle super.addAll, qui je suppose sera résultat en O(n logn).

MODIFIER deviner, j'ai lu le code trop vite, TreeSet ne peut utiliser l'algorithme O(n) si c'est la sauvegarde de la carte est vide

OriginalL'auteur Chris Arnold
1

Selon ce blog:

http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html

il est O(n log n). Parce que la documentation donne pas de conseils à propos de la complexité, vous pouvez écrire votre propre algorithme si la performance est critique pour vous.

OriginalL'auteur Karel Petranek
0

Il n'est pas possible d'effectuer la fusion d'arbres ou d'adhérer à des ensembles comme dans Disjoints-définir des structures de données parce que vous ne savez pas si les éléments dans les 2 arbres sont disjoints. Depuis les structures de données ont des connaissances sur le contenu des autres arbres, il est nécessaire de vérifier si un élément existe dans l'autre arbre avant de l'ajouter à, ou au-moins essayer d'ajouter dans un autre arbre de l'abandon et de l'ajouter si vous le trouvez sur le chemin.
Donc, il faut O(MlogN)

Je ne comprends pas très bien cette. Supposons que vous avez deux SortedSets qui n'ont pas d'-les éléments qui se chevauchent et qui sont représentés par des arbres rouge-noir. Comment se fait que vous ne pouvez pas vous joindre à eux depuis le "rejoindre" l'opération dans les arbres rouge-noir prendre en O(log(n+m)) de temps?
2 arbitraires TreeSets, comment allez-vous savoir si c'est le cas?
Ainsi, selon le programme que je suis en train de faire, je peux vous garantir que les deux TreeSets n'aurez pas de chevauchement de l'élément. Cependant, il semble que je ne suis pas en mesure de se joindre à eux en O(log(n+m)) comme l'a souligné le reste des réponses...

OriginalL'auteur user855

Vous devez vous connecter pour publier un commentaire.