¿Se pueden ordenar n enteros en O (n) complejidad amortizada?

Question

¿Es teóricamente posible ordenar una matriz de n enteros en una complejidad amortiguada de O (n)?

¿Qué tal si intentamos crear el peor caso de complejidad O (n)?

La mayoría de los algoritmos actuales se basan en el promedio de O (nlogn) + O (n^2) en el peor de los casos. Algunos, al usar más memoria son O (nlogn) los peores.

¿Puede usted sin limitaciones en el uso de la memoria crear dicho algoritmo? ¿Qué pasa si su memoria es limitada? ¿Cómo afectará esto a tu algoritmo?

Answer 1

cualquier página en el intertubes que se ocupa de las clases basadas en la comparación will tell you que no puede tipo más rápido que con O(n lg n) tipo de comparación. Es decir, si su algoritmo de clasificación decide el orden comparando 2 elementos entre sí, no puede hacer nada mejor que eso. Los ejemplos incluyen quicksort, bubblesort, mergesort.

Algunos algoritmos, como el ordenamiento por recuento o el ordenamiento del cubo o la ordenación por radix no usan comparaciones. En cambio, dependen de las propiedades de los datos en sí, como el rango de valores en los datos o el tamaño del valor de los datos.

Esos algoritmos pueden tener complejidades más rápidas. Aquí es un escenario de ejemplo:

está ordenando 10^6 enteros, y cada número entero entre 0 y 10. Luego puedes contar el número de ceros, unos, dos, etc. y escupirlos en orden ordenado. Así es como funciona countort, en O(n + m), donde m es el número de valores que su dato puede tomar (en este caso, m=11).

Otra:

está ordenando 10^6 cadenas binarias que son todos como máximo 5 caracteres de longitud. Puede usar el orden de radix para eso: primero divídalos en 2 segmentos dependiendo de su primer carácter, luego clasifique por radix para el segundo carácter, tercero, cuarto y quinto. Siempre que cada paso sea estable, debe terminar con una lista perfectamente ordenada en O(nm), donde m es el número de dígitos o bits en su datum (en este caso, m=5).

Pero en el caso general, no se puede ordenar con mayor rapidez que O(n lg n) de forma fiable (utilizando una clasificación de comparación).

Answer 2

Creo que está buscando radix sort.

Answer 3

Si los enteros están en un rango limitado, entonces un O (n) "orden" de ellos implicaría tener un vector de bits de "n" bits ... bucle sobre los enteros en cuestión y establecer el n% 8 bit del desplazamiento n // 8 en ese conjunto de bytes a verdadero. Esa es una operación "O (n)". Otro bucle sobre ese conjunto de bits para enumerar/enumerar/devolver/imprimir todos los bits establecidos es, asimismo, una operación O (n). (Naturalmente O (2n) se reduce a O (n)).

Este es un caso especial donde n es lo suficientemente pequeño como para caber dentro de la memoria o en un archivo (con operaciones seek()).No es una solución general; pero está descrito en "Programming Pearls" de Bentley --- y supuestamente era una solución práctica a un problema del mundo real (que involucraba algo así como un "freelist" de números de teléfono ... algo así como: encuentre el primer número de teléfono disponible que podría ser emitido a un nuevo suscriptor).

(Nota: log (10 * 10) es ~ 24 bits para representar cada posible número entero de hasta 10 dígitos de longitud ... así que no hay mucho espacio en 2 * 31 bits de una típica máxima de Unix/Linux mapeo de memoria de tamaño).

Answer 4

No estoy del todo contento con la respuesta aceptada hasta el momento. Así que estoy volviendo a intentar una respuesta:

¿Es teóricamente posible ordenar una matriz de n enteros en una complejidad amortiguada de O (n)?

La respuesta a esta pregunta depende de la máquina que ejecutará el algoritmo de clasificación. Si tiene una máquina de acceso aleatorio, que puede funcionar exactamente en 1 bit, puede hacer radix sort para enteros con un máximo de k bits, que ya se sugirió. Entonces terminas con la complejidad O(kn).
Pero si está trabajando en una máquina de palabra de tamaño fijo con un tamaño de palabra de al menos k bits (que son todas las computadoras de consumo), lo mejor que puede lograr es O(n log n). Esto se debe a que o bien log n < k o bien podría hacer un count sort primero y luego ordenarlo con un algoritmo O (n log n), lo que arrojaría también el primer caso.

¿Qué tal si intentamos crear el peor caso de complejidad de O (n)?

Eso no es posible. Un enlace ya fue dado. La idea de la prueba es que para poder ordenar, debe decidir para cada elemento que se ordenará si es más grande o más pequeño que cualquier otro elemento que se va a ordenar. Al utilizar la transitividad, esto se puede representar como un árbol de decisión, que tiene n nodos y log n de profundidad en el mejor de los casos. Por lo tanto, si desea tener un rendimiento mejor que Ω(n log n), esto significa eliminar los bordes de ese árbol de decisión. Pero si el árbol de decisiones no está completo, ¿cómo puede asegurarse de haber tomado una decisión correcta sobre algunos elementos a y b?

¿Puede usted sin limitaciones en el uso de la memoria crear tal algoritmo?

Así que, como desde arriba no es posible. Y las preguntas restantes son, por lo tanto, irrelevantes.