El problema: se nos da una lista de N “X precede inmediatamente a las relaciones Y”. Nos gustaría ordenar las entradas con nombre N + 1 en el orden descrito por la entrada.
Aquí hay un pequeño ejemplo. Si le dicen que “5 precede a 3” y “2 precede a 5”, puede producir fácilmente la salida 2 5 3.
Si la memoria no es un problema: existe una solución de tiempo O (N) perfectamente buena para generar los elementos en el orden descrito por la entrada.
- ¿Dónde puedo encontrar una biblioteca de estructura de datos de gráficos dirigida, implementada en Javascript?
- ¿Puedes darme una idea para un juego simple que implemente el algoritmo (como el algoritmo A *) o la inteligencia artificial para NPC en el juego?
- ¿Qué calcula este algoritmo? ¿Cuál es su funcionamiento básico? ¿Cuántas veces se ejecuta la operación básica? ¿Cuál es la clase de eficiencia de este algoritmo?
- ¿Cuál es el algoritmo para resolver el buscaminas?
- ¿Cuáles son algunos problemas de práctica en la estructura de datos de árbol en sitios web competitivos?
1) Construya una asignación de índice X a su sucesor Y (esto podría ser una tabla hash u otra cosa) y un índice inverso de todas las entradas que tienen predecesoras.
2) Explore las entradas buscando la entrada única S que no tiene predecesora (usando el índice inverso)
3) Comenzando con S, busque cada entrada en el índice y siga la cadena de relaciones de “ingresos inmediatos” hasta que obtengamos todas las entradas en el orden especificado.
Pero, nuestro índice es de tamaño O (N) y se accede en orden aleatorio. Para cualquier conjunto de datos de tamaño razonable, esto no es un problema. Por lo tanto, debemos imaginar una información de tamaño irracional demasiado grande para indexarla en la memoria.
La solución de Norman Hardy es útil para un caso restringido en el que tenemos que hacer un acceso secuencial a los datos, como la cinta. Podemos usar cinta adicional si la necesitamos, pero la cantidad de memoria es limitada. Como primitivo, Hardy supone que ya sabemos cómo ordenar N entradas en un orden fijo . Por ejemplo, orden numérico o alfabético, distinto del orden de entrada. (La clasificación de un gran conjunto de datos con memoria limitada y orden secuencial también es un problema interesante, pero no se aborda aquí. Puede considerarlo como dividir y conquistar más un pase de fusión final).
Nuestra entrada es [math] (x_i, x_ {i + 1}) [/ math] pares, donde [math] i [/ math] es su índice en el orden deseado. Si hacemos dos copias y clasificamos A por el primer componente y B por el segundo componente, entonces podemos hacer una operación de “unión”. El primer elemento de B es un par (X -> 1), y el primer elemento de A es (1-> Y), por lo que al unirlos tenemos el fragmento (X-> 1-> Y). (Solía 1 para indicar que este elemento está primero en el orden de clasificación fijo).
Entonces, como resultado de esta primera fase, obtenemos dos cosas. Obtenemos un conjunto de pares [math] (x_i, x_ {i + 2}) [/ math] de elementos que están separados por dos pasos en el orden de entrada. Menos obvio, también encontramos los elementos últimos y penúltimos del orden de clasificación de entrada, porque hay algo de L tal que (X-> L) está en la lista B pero (L -> ???) no existe en la lista A. Eso nos dice que L es el último elemento y X es el penúltimo. Entonces, comencemos a construir nuestro orden de salida final como (N + 1, L) y (N, X) en otro archivo, con cada elemento emparejado con su índice en el orden final.
Luego, repetimos el proceso, construyendo elementos que están a una distancia de 4, 8, 16, etc. y duplicando la longitud del orden de salida final conocido. Como antes, clasifiquemos los archivos en un orden útil:
B contiene [matemáticas] (x_i, x_ {i + t}) [/ matemáticas] en el orden del segundo componente; llama al elemento actual que estamos leyendo [math] (b, b_ {next}) [/ math]
A contiene [math] (x_i, x_ {i + t}) [/ math] en el orden del primer componente. De manera similar, llamemos al elemento actual [math] (a, a_ {next}) [/ math]
G contiene [math] (i, x_i) [/ math] en el orden del segundo componente (la entrada, no su índice). Llamar al elemento actual [math] (g_ {index}, g) [/ math]
(1) Si [math] b_ {next} = a [/ math], entonces hemos encontrado dos elementos que están separados [math] 2t [/ math], de modo que la salida [math] (b, a_ {next}) [ / math] que tiene la forma [math] (x_i, x_ {i + 2t}) [/ math]. Pase a las siguientes entradas en A y B.
(2) si [math] b_ {next} = g [/ math], entonces hemos encontrado el elemento que es ‘t’ pasos antes de la posición conocida [math] g_ {index} [/ math]. Ponga [math] (g_ {index} – t, b) [/ math] en nuestro orden de salida final. Pase a los siguientes elementos en B y G.
(3) si [math] b_ {next}> g [/ math], usando el orden fijo, entonces lea la siguiente entrada del archivo G. [math] b_ {next} [/ math] podría ser útil para el paso (2 ), por lo que aún no podemos deshacernos de él, pero sabemos por el orden de clasificación que no encontraremos una coincidencia para [math] g [/ math].
(4) si [math] b_ {next}> a [/ math], usando el orden fijo, avanza A
Continúe hasta que agotemos B. De esta manera duplicamos el número de elementos conocidos.
Suponga que [matemáticas] N = 100 [/ matemáticas]. En la primera pasada aprendimos [matemáticas] x_ {101} [/ matemáticas] y [matemáticas] x_ {100} [/ matemáticas]. En la segunda pasada, podemos retroceder dos pasos, por lo que aprendemos [matemáticas] x_ {99} [/ matemáticas] y [matemáticas] x_ {98} [/ matemáticas]. En el tercer pase podemos retroceder cuatro pasos, por lo que aprendemos [matemáticas] x_ {94} [/ matemáticas], [matemáticas] x_ {95} [/ matemáticas], [matemáticas] x_ {96} [/ matemáticas], y [matemáticas] x_ {97} [/ matemáticas].
En [math] O (\ log_2 N) [/ math] pasa habremos aprendido la ubicación final de cada elemento, y podemos ordenar nuestra lista G por los números de índice (primer componente) para obtener la salida. Solo necesitamos una cantidad de cinta que sea un pequeño múltiplo del tamaño de entrada. ¡Pero tenga en cuenta que también hicimos [math] O (\ log_2 N) [/ math] tipos de la mitad o más de la entrada!
Puede ser útil para comprender este algoritmo dividir los pasos 1–4 en dos procesos separados. Uno construye la lista “2t” para la próxima iteración, y uno aplica la lista “t” a las posiciones conocidas actualmente. Para mayor eficiencia, se escriben como procesos intercalados, pero no afecta el análisis asintótico big-O si los realiza como dos pases separados.
