5
He mirado en diferentes papeles y aquí es la información que he reunido:¿Cuál es la complejidad de concatenación de cuerdas balanceadas?
- SGI implementation y C cords ni garantiza O (1) tiempo de concatenación de cuerdas largas ni ~ log N de profundidad para los más cortos .
- Diferentes fuentes se contradicen entre sí. Wikipedia afirma O (1) concatenación. This page dice que la concatenación es O (1) solo cuando un operando es pequeño y O (log N) en caso contrario.
Entonces, ¿cuál es la complejidad de tiempo de la concatenación? ¿Cuándo se realiza un reequilibrio exacto para garantizar esta complejidad de concatenación mientras se mantiene el equilibrio del árbol? ¿Se asumen algunos patrones de uso específicos cuando se habla de esta complejidad?
todas las operaciones son 'log (N)' complejidad de tiempo. Rope esencialmente es un árbol de búsqueda binaria compuesto de claves implícitas, que por naturaleza se refieren al tamaño del subárbol. Eso permite operaciones potentes tales como concat/split. Una de las posibles implementaciones es usar una estructura de datos Treap, que está hecha a propósito para trabajar con claves implícitas y con alta probabilidad de mantener la altura del árbol dentro del rango '4 * log (n)', que es 'O (log n) '. He hecho una implementación simple de ella usando Treap: https://ideone.com/uMt0Mi. – Yerken
@ Yerken: gracias, ya que hice esta pregunta, yo mismo implementé las cuerdas, con una complejidad determinística 'log N 'determinística. Parece que la concatenación 'O (1)' es un concepto erróneo extendido por algunas personas, hacerlo en 'O (log N)' es trivial. He echado un vistazo a su código, pero no parece ajustarse a las implementaciones de sogas: si utiliza punteros padres, debe clonar todo el árbol (en el tiempo 'O (N)') cuando realice cambios locales. El punto de las cuerdas es que evitan eso. – ybungalobill
lo siento, no lo entiendo, ¿qué quiere decir clonar todo el árbol? Todos los cambios locales se realizan a través de fusionar y dividir, que se realizan solo a lo largo de la línea de corte (donde los punteros están desreferenciados) que es una altura del árbol – Yerken