¿Alguien está familiarizado con el algoritmo de clasificación de enteros Yijie Han ? Este resultado aparece en un artículo bastante corto ( Clasificación determinista en tiempo O ( n log log n ) y espacio lineal . J. Alg. 50: 96–105, 2004) que básicamente reúne muchos resultados anteriores, con adaptaciones adecuadas. Mi problema es que está escrito de una manera bastante agitada sin profundizar en detalles. Se basa en gran medida en documentos anteriores, destacando entre ellos otro artículo de Han ( clasificación de números enteros rápida mejorada en espacio lineal. Information and Computation 170 (1): 81–94) escrito en el mismo estilo. Tengo dificultades significativas para comprender estos dos documentos, particularmente la forma en que se adaptan y usan los resultados anteriores. Apreciaría cualquier ayuda.
Por supuesto, esto es demasiado amplio y vago para ser considerado una pregunta adecuada, pero espero desarrollar una discusión a través de varias preguntas y respuestas bien definidas.
Para comenzar, aquí está mi primera pregunta específica. En el Lema 2 de la Información. Comp. En el documento hay un algoritmo de tiempo recursivo para encontrar el enésimo número entero más pequeño en un conjunto de n enteros pequeños empaquetados k cada uno en palabras RAM. La descripción del algoritmo no menciona cómo se maneja el caso base k = O ( n ) . En este caso se requiere hacer la selección en tiempo O ( log k ) . ¿Cómo se puede hacer esto?
Respuestas:
Me preguntaba lo mismo.
Afortunadamente, pude encontrar un artículo de revista publicado en 2011 que explica esto mismo; además, no necesita una suscripción para verlo: Implementación y análisis de rendimiento de la ordenación exponencial de árboles
Recomiendo leer el artículo completo para aprender cómo se puede implementar y comprender mejor su teoría subyacente. También muestra cómo los árboles exponenciales se comparan con los árboles binarios y de clasificación rápida. Aquí está el extracto relevante relacionado con el tiempo de Han , espacio lineal, algoritmo de clasificación de enterosO ( n logIniciar sesiónn ) :
[6] Y. Han, clasificación determinista en O (n log log n) tiempo y espacio lineal, 34 ° STOC, 2002.
[8] A. Andersson, clasificación y búsqueda deterministas rápidas en el espacio lineal, Simposio IEEE sobre Fundamentos de Ciencias de la Computación, 1996.
fuente
No estoy seguro de la respuesta (no he revisado el documento) pero creo que esto debería ayudar. Los números se agrupan en una sola palabra, por lo que las operaciones en una sola palabra toman O (1) tiempo. Si hay, digamos, k números de h bits cada uno, entonces el tamaño de la palabra depende de k, h que a su vez también depende del rango de números. Por lo tanto, utilizamos técnicas de reducción de rango que pueden reducir el rango de números para que muchos números quepan en una sola palabra. Luego, creando máscaras de bits adecuadas, podemos encontrar enteros más grandes separados de los más cortos considerando dos palabras a la vez. Esto se puede hacer en O (1) tiempo. (Ontuición: para esto, cada número almacenado en la palabra tiene un bit indicador asociado y luego restamos dos palabras ... si el bit indicador desaparece, entonces es un número menor).
De manera similar, utilizando el anterior también podemos ordenar cualquier palabra que contenga k números en el tiempo O (log k) (ordenación bitónica).
Editar: Algoritmo para ordenar 2k números en el rango de 0 a m-1 empaquetados en una palabra donde cada número toma el tamaño L de = log (m + k) +2.
sea 1: 000000 1: 000000 1: 000000 1: 000000 ....... etc., donde el bit antes de los dos puntos también se llama bit indicador y cada secuencia tiene una longitud de L bits y se repite 2k veces en la palabra K_1 (Colon es solo para entender)K1
es (2k-1) (2k-2) .... 1 escrito en binario. Bosquejo del algoritmo:K2
Repita para t = log k a 0.
Parte 1: separe la palabra original Z en dos palabras A y B.
Sea T obteniendo desplazando , (posiciones L-1-t) a la izquierda y ANDing el resultado con K 1 . Deje M = T- (T desplazado L-1 lugares).K2 K1
B = Z- (Z&M).
Parte 2
M = M- (M desplazado a la izquierda L-1 lugares).
MIN = (B&M) OR (A- (A&M))
MAX = (A&M) OR (B- (B&M))
Finalmente apropiadamente ORing MAX y MIN regresamos Z.
He dado el boceto, espero que pueda completar los detalles necesarios requeridos.
fuente