¿Cuál es la complejidad de tiempo de las siguientes operaciones en java.util.TreeSet?¿Cuál es la complejidad de tiempo de las operaciones ordenadas en TreeSet?
first()last()lower()higher()quiero suponer que se trata de tiempo constante, pero la API no ofrece ninguna garantía.
En realidad, hubiera pensado que todas esas operaciones van a ser O(logN) para una implementación general.
Para first() y last() para ser O(1) la implementación TreeSet necesitaría mantener un puntero a los nodos extremos izquierdo y derecho de la hoja en el árbol, respectivamente. El mantenimiento de estos agrega un costo constante a cada inserción y al menos un costo constante para cada eliminación. En realidad, la implementación probablemente encuentre los nodos de izquierda/derecha sobre la marcha ... que es una operación O(logN).
Los métodos lower() y higher() tienen que hacer el mismo trabajo que get y son por lo tanto O(logN).
Por supuesto, usted puede verificar el código fuente usted mismo para ver qué sucede en realidad.
La API no ofrece garantías porque se basan en el modelo estándar de un trie. El mejor de los casos es O (1), siendo el caso promedio O (log n) y el peor caso O (n).
De la documentación:
Esta aplicación proporciona registro de garantía (n) Coste tiempo para las operaciones básicas (añadir, eliminar y contiene).
Estas no son las funciones que solicitó, pero piense cómo Java atravesará el TreeSet.
Va a depender de la implementación. No estoy muy familiarizado con JAVA, pero parece que todas esas operaciones son operaciones transversales (obtener el elemento más bajo, obtener el elemento más alto, obtener el siguiente más alto o el siguiente más bajo).
Si el árbol está implementado como Self-Balancing Binary Search Tree como AVL Tree, o cualquier otro tipo de estructura de árbol balanceado, usted va a estar mirando el tiempo de caja promedio y peor-caja O (log n) para cada de las operaciones, y un mejor caso de O (1).
Pero la implementación se especifica como un árbol Rojo-Negro, por lo que no depende de la implementación. – EJP
Parece que tanto primera() y la última() será O (log n) y no O (1) basado en implementació (Sun JDK 1.6.0_23) de TreeMap que es utilizado por TreeSet por defecto:
/**
* 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;
}
De hecho, busqué el código fuente, en http://developer.classpath.org/doc/java/util/TreeSet-source.html, first() llamadas mapas.firstKey() después en http://developer.classpath.org/doc/java/util/TreeMap-source.html
393: public K firstKey()
394: (
395: if (root == nil)
396: throw new NoSuchElementException();
397: return firstNode().key;
398:)
y en firstNode(), que hace el bucle while para recorrer todo el camino a la
izquierda952: final Node<K, V> firstNode()
953: (
954: // Exploit fact that nil.left == nil.
955: Node node = root;
956: while (node.left != nil)
957: node = node.left;
958: return node;
959:)
Miré el código fuente pero es demasiado abstracto. No estoy seguro de dónde se implementan el primero y el último. Tengo que buscar más. – signalseeker
TreeSet se implementa internamente con un TreeMap, por lo que la mayor parte de la lógica está en 'TreeMap.get [First | Last | Lower | Higher] Entry()'. Todos atraviesan el árbol para encontrar los nodos, de modo que Stephen C es correcto, O (log N). – SimonC