En lugar de solo encontrar la mediana, aquí hay un algoritmo eficiente para encontrar el késimo elemento más pequeño en un rango.
Cree un árbol de rango ortogonal bidimensional creado a partir de los N puntos de la forma (A [i], i). La construcción de este árbol se puede hacer fácilmente en tiempo O (N log ^ 2 N) (aunque es posible O (N log N)).
Ahora, para consultar el elemento k, atravesamos la primera dimensión del árbol. Seguimos el subárbol izquierdo si el número de puntos dentro de nuestro rango de índice de consulta en el subárbol izquierdo es menor que k. Esto es simplemente una consulta en el árbol de segunda dimensión del subárbol izquierdo. Si el elemento kth no está en el subárbol izquierdo, ajustamos k adecuadamente y buscamos en el subárbol derecho. Toda esta búsqueda lleva O (N log ^ 2 N) tiempo. Esencialmente, hemos eliminado un factor log N de la solución de Johnny envolviendo la búsqueda binaria en el recorrido del árbol.
- ¿Qué es una explicación intuitiva de P = NP?
- Puedo tomar la teoría de grafos o la combinatoria el próximo semestre. Me interesa la informática teórica. ¿Cuál sería mejor?
- Cómo resolver problemas sobre el análisis de algoritmos paso a paso
- Las matemáticas se han desarrollado mucho en los primeros períodos, pero el desarrollo de la ciencia se retrasa. ¿Por qué?
- Cómo imprimir el conjunto de potencia de un conjunto finito de enteros en Java usando recursividad
En realidad, es posible reducir esto a O (N log N) preprocesamiento y O (log N) por consulta. Pase a aproximadamente las 17:00 en 6.851: Estructuras de datos avanzadas (Spring’12) para ver a Erik Demaine explicar los árboles de rango ortogonales y cómo lograr tiempos de preprocesamiento y consulta más rápidos que requieren una leve inteligencia y una cascada fraccional respectivamente.
