Intentemos esto.
Asumiré algo: las cadenas se representan como un objeto en el montón y se accede a ellas a través de una referencia (como en Java). Esto es importante porque en este caso, “asignar” una cadena es O (1).
01110
10100
00100
10110
10101
Realizará una iteración de clasificación de Radix (sección Implementaciones de clasificación de radix MSD in situ ) Pero solo una iteración, usando los bits en la primera columna. Después de eso, la matriz debería verse así:
- ¿Cómo podemos decir que un número es primo usando su raíz cuadrada?
- ¿Cuál es el mayor problema que enfrentamos hoy y qué ciencias de la tierra pueden ayudar a resolver este problema?
- ¿Cómo se debe resolver este problema en un método más simple y rápido?
- ¿Por qué algunos maestros se enojan si encuentras una manera más simple de resolver un problema?
- ¿Cuál es el ángulo entre la manecilla de hora y minutos de un reloj cuando son las 4:20 pm? ¿Cuál es el método para resolver esta pregunta?
01110
00100
10110
10101
10100
(Las filas no están en la posición original porque el procedimiento no es estable)
Este primer paso se realiza en O (1), y la única memoria consumida en la memoria utilizada para almacenar las cadenas. Ahora podemos centrarnos en el bloque con menos filas; en este caso, las filas con el primer bit = 0. Observe a continuación cómo estas dos filas comparten el mismo prefijo. Tenga en cuenta también que las otras filas tienen un prefijo diferente.
01110
00100
Repita las cosas de Radix Sort pero usando la segunda columna.
00100
01110
Como ambos bloques tienen el mismo tamaño, podemos conservar cualquiera de ellos.
00100
Y ahora casi hemos terminado. Tenemos una sola fila. Si solo tenemos una fila, ¿qué podemos decir de todas las demás? Todos ellos tienen un prefijo diferente de longitud m , donde m es el número de iteraciones requeridas para construir un bloque de solo una fila.
¿Cuál es la nueva cadena? Reemplace el bit m en la cadena por su complemento.
00100 -> 00000
¿El tiempo de ejecución es O (n ^ 2)? Si el método que cité es O (n) como creo, sí. Simplemente porque tenemos que usarlo como máximo n veces (n columnas).
¿Es O (1) memoria? Bueno, aparte de la memoria para almacenar las cuerdas, sí. Solo necesitamos un puñado de índices.
¿Es esto siempre correcto? Uhmmm … creo que sí, pero no tengo una prueba.
Finalmente, a la explicación le falta un caso de esquina, cuando todas las filas de un bloque tienen el mismo prefijo. Esto es fácil de detectar y manejar.