Quelle est la complexité de temps des opérations suivantes dans java.util.treseset ?
premier ()
-
dernier ()
-
inférieur ()
-
plus élevé ()
Je suppose que celles-ci sont une durée constante, mais l'API ne fait aucune garantie.
5 Réponses :
L'API ne fait aucune garantie car celles-ci sont basées sur le modèle standard d'une trie. Le meilleur cas est dans O (1), avec le cas moyen étant O (journal n) et le pire des cas O (n).
de la documentation:
Cette implémentation fournit un journal garanti (n) coût de temps pour les opérations de base (ajouter, supprimer et contenir).
Ce ne sont pas les fonctions que vous avez demandées, mais réfléchissez à la façon dont Java traversera les arbres.
Haha yeh, corrigé-le maintenant;)
En réalité, j'aurais pensé que ces opérations seront toutes pour Le Bien sûr, vous pouvez vérifier le code source vous-même pour voir ce qui se passe réellement. (Comme d'autres personnes ont fait: voir ci-dessous.) O (logn) pour une mise en œuvre générale.
premier () et dernier (() doit être o (1) L'implémentation de l'arbre aurait besoin de maintenir un pointeur aux nœuds les plus à gauche et à droite dans l'arbre respectivement. Le maintien de ceux-ci ajoute un coût constant à chaque insertion et au moins un coût constant à chaque délétion. En réalité, la mise en œuvre trouvera probablement les nœuds latéraux gauche / à droite sur la mouche ... qui est un O (logn) opération.
inférieur () et plus haut () Les méthodes doivent faire le même travail que obtenir et sont donc O (logn) .
J'ai pris au regard du code source mais c'est trop abstrait. Je ne suis pas sûr où le premier et le dernier est mis en œuvre. Faut-il regarder d'autres.
Le Treeet est mis en œuvre en interne avec un Treemap, la plupart de la logique se trouvent dans Treeemap.get [premier | Dernier | Dernier (Dernier | Higher] Entrée () . Tous traverser l'arborescence pour trouver les nœuds afin que Stephen c soit correct, O (log n).
Cela dépend de la mise en œuvre. Je ne connais pas incroyablement avec Java, mais il semble que toutes ces opérations soient des opérations triviatoires (obtenez l'élément le plus bas, obtenez l'élément le plus élevé, obtenez-vous ensuite plus haut ou plus bas).
Si l'arborescence est implémentée comme un arbre de recherche binaire auto-équilibré comme un < un href = "http://en.wikipedia.org/wiki/avl_tree" rel = "nofollow"> AVL Tree ou tout autre type d'une structure d'arborescence équilibrée, vous allez regarder Durée moyenne et pire des cas O (log n) Temps pour chacune des opérations et un meilleur cas de O (1).
Mais la mise en œuvre est spécifiée comme un arbre noir rouge, de sorte que cela ne dépend pas de la mise en œuvre.
On dirait que les deux premiers () et la dernière () seront O (log n) et non O (1) en fonction de l'implémentation (Sun JDK 1.6.0_23) de Treeemap, utilisé par Arbreset par défaut:
/**
* Returns the first Entry in the TreeMap (according to the TreeMap's
* key-sort function). Returns null if the TreeMap is empty.
*/
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
/**
* Returns the last Entry in the TreeMap (according to the TreeMap's
* key-sort function). Returns null if the TreeMap is empty.
*/
final Entry<K,V> getLastEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.right != null)
p = p.right;
return p;
}
Je regardais en fait le code source,
Dans http://developer.classpath.org/doc/java/util/java/util/ Arbreset-source.html , premier () appels mapss.firstSkey ()
puis dans
http://developer.classpath.org/doc/java/util/tremap -source.html et en firstNode (), il fait la boucle tandis que la boucle est allumée jusqu'à la gauche