Debido al espacio de dominio finito de los datos (es decir, “enteros”), se puede resolver en una variante de [matemática] O (n) [/ matemática] que, en ciertos escenarios, es mejor que la ordenación regular. Como el presidente Obama dice correctamente, “Bubble Sort no es el camino a seguir”.
Primero, examinemos cómo se pueden ordenar los datos con un espacio de dominio finito (como Enteros de 32 bits) en tiempo lineal:
Un ejemplo es el tipo Radix:
para el índice j de cero a 31
cubo de clasificación de enteros por su jésimo índice desde el lado derecho // O (n)
La complejidad de esta clasificación es [matemática] O (lg (domainSize) * n) [/ matemática] en este caso [matemática] O (32 * n) [/ matemática], equivalente a [matemática] O (n) [/ matemáticas] o lineal. En inglés simple, pones n números binarios en dos cubos cero o uno, 32 veces. Ignora esos multiplicadores constantes y tienes un proceso lineal.
Ejemplo en decimales de 3 dígitos:
431, 235, 521, 236
después del primer pase (ordenar por el extremo derecho): 431, 521, 235, 236
después del segundo pase (ordenar por medio dígito): 521, 431, 235, 236
después del tercer pase (ordenar por el extremo izquierdo): 235, 236, 431, 521
En este ejemplo, necesita 10 cubos (es decimal) y 3 pasa a través de los datos (son 3 dígitos)
En el caso entero general, necesita 2 cubos (es binario) y 32 pasa a través de los datos. Entonces, la complejidad es [matemática] O (32 * n) [/ matemática] que es [matemática] O (n) [/ matemática], o lineal.
A veces, según el múltiplo lineal y el tamaño de los datos, [matemática] O (n * lg (n)) [/ matemática] es mejor que [matemática] O (n) [/ matemática]
Pensándolo bien, tenga en cuenta que [matemática] O (n) [/ matemática] es solo mejor que [matemática] O (n * lg (n)) [/ matemática] cuando el tamaño de los datos se aproxima al infinito. En este caso particular, dado que tenemos un número conocido de puntos de datos (1 millón), la ventaja de utilizar la ordenación lineal como hemos demostrado no necesariamente entra en acción. La ordenación lineal, como hemos observado, toma [matemática] O (32 * n) [/ math], pero el orden regular toma:
[matemática] O (n * lg (n)) = O (n * lg (1M)) ~ = O (20 * n) [/ matemática]
Entonces, la ordenación regular es claramente mejor que la solución lineal anterior, y esto es cierto hasta 32 cubos y un millón de enteros.
¡Pero espera! Hay espacio para la optimización.
Por lo tanto, demostramos que la ordenación regular en datos finitos es tan buena como cualquier ordenación lineal (por ejemplo, Radix), siempre que el múltiplo de [math] n [/ math] en la complejidad del algoritmo de ordenación lineal sea peor que (mayor o igual que ) 20, requerido por la ordenación regular (Recuerde que 20 es el número mágico para la comparación binaria entre un máximo de 1,000,000 de enteros, y la comparación binaria se usa en la ordenación regular).
El desafío es el siguiente: ¿Podemos diseñar un tipo Radix que produzca un multiplicador “k” en complejidad lineal [matemática] O (k * n) [/ matemática] que sea menor que 20?
Recuerde que el multiplicador en la clasificación Radix es el número de cubos. En nuestro algoritmo anterior, utilizamos 32 cubos. ¿Podemos usar menos?
Porque?, si. Veamos qué sucede si definimos nuestro cubo como cada dos bits:
para el índice j de cero a 31 paso a paso por 2
tipo de cubo enteros por su j + 1 y j'th bit del lado derecho // O (n)
Esto para el bucle se ejecuta 16 veces. Entonces, la complejidad de este ordenamiento lineal es [matemática] O (16 * n) [/ matemática] o mejor que el ordenamiento regular, incluso para estos datos finitos.
Entonces, ¿dónde está el límite inferior?
Es tentador tratar de llevar esto al límite. ¿Por qué no simplemente hacer un cubo de cada entero único y hacer una clasificación de Radix en eso? ¿Seguramente eso será solo una pasada o [matemáticas] O (1 * n) [/ matemáticas]?
No tan rapido. En la aproximación “aproximada” inicial de la complejidad del ordenamiento Radix, pasamos por alto el costo de fusionar los cubos, porque solo teníamos dos cubos para cada una de las 32 iteraciones.
La verdadera complejidad de una clasificación Radix es [matemática] O (k * (n + 2 ^ b)) [/ matemática] para enteros de 32 bits, donde [matemática] k * b == 32 [/ matemática]. k es el número de veces que el Entero se “divide” en el algoritmo (el número de iteraciones) y, por lo tanto, b es el número de bits que debemos observar para descubrir la clave del depósito. Por lo tanto, hay cubos [matemática] 2 ^ b [/ matemática] y en cada iteración necesitamos visitar cada uno de ellos para recopilar los resultados.
Probemos esto para algunas configuraciones de k y b (donde eventualmente n es sustituido por [math] 2 ^ {20} [/ math], que es una aproximación cercana para 1M):
k = 32 (es decir, 2 cubos):
[matemáticas] O (32 * (n + 2)) = O (32n + 2 ^ 6) [/ matemáticas]
[matemáticas] \ aprox. O (2 ^ {25} + 2 ^ 6) \ aprox. O (2 ^ {25}) [/ matemáticas]
k = 16 (es decir, 2 ^ 2 cubos):
[matemáticas] O (16 * (n + 2 ^ 2)) = O (16n + 2 ^ 6) [/ matemáticas]
[matemáticas] \ aprox. O (2 ^ {24} + 2 ^ 6) \ aprox. O (2 ^ {24}) [/ matemáticas]
k = 8 (es decir, 2 ^ 4 cubos):
[matemáticas] O (8 * (n + 2 ^ 4)) = O (8n + 2 ^ 7) [/ matemáticas]
[matemáticas] \ aprox. O (2 ^ {23} + 2 ^ 7) \ aprox. O (2 ^ {23}) [/ matemáticas]
k = 4 (es decir, 2 ^ 8 cubos):
[matemáticas] O (4 * (n + 2 ^ 8)) = O (4n + 2 ^ {10}) [/ matemáticas]
[matemáticas] \ aprox. O (2 ^ {22} + 2 ^ {10}) \ aprox. O (2 ^ {22}) [/ matemáticas]
k = 2 (es decir, 2 ^ 16 cubos):
[matemáticas] O (2 * (n + 2 ^ {16})) = O (2n + 2 ^ {17}) [/ matemáticas]
[matemática] \ aprox. O (2 ^ {21} + 2 ^ {17}) \ aprox. O (2 ^ {21}) [/ matemática]
k = 1 (es decir, 2 ^ 32 cubos):
[matemáticas] O (1 * (n + 2 ^ {32})) = O (n + 2 ^ {32}) [/ matemáticas]
[matemáticas] \ aprox. O (2 ^ {20} + 2 ^ {32}) \ aprox. O (2 ^ {32}) [/ matemáticas]
Tenga en cuenta que al disminuir el número de iteraciones a uno (y aumentar el número de cubos que se representarán por todos los 32 bits, en la última línea), el costo de cómputo diverge debido a la sobrecarga de los cubos visitantes.
La respuesta óptima es en algún lugar entre k = 2 ([matemática] 2 ^ {16} [/ matemática] cubos) y k = 4 ([matemática] 2 ^ 8 [/ matemática] cubetas), y depende de la cantidad de gastos generales. pasé fusionando cubos de nuevo juntos. De acuerdo con experimentos prácticos de Anders y otras personas en este hilo, parece que Radix sortear con [math] 2 ^ 8 [/ math] es el ganador .
Dejaré el escenario de procesamiento paralelo al lector.
Por cierto, el presidente tiene razón, porque Bubble Sort tomaría [math] O (n ^ 2) [/ math] o, en este caso, aproximadamente [math] O (2 ^ {40}) [/ math].
(Editado con especial agradecimiento a los comentarios de Anders, Ryan, Erik y Sergei!)
