performance - sheet - ¿Cuáles son las reglas para la "barrera Ω(n log n)" para los algoritmos de clasificación?

algorithm complexity examples

Question

Escribí un programa simple que ordena en O (n). Es altamente ineficiente en la memoria, pero ese no es el punto.

Utiliza el principio detrás de un HashMap para clasificar:

public class NLogNBreak {
    public static class LinkedListBack {
        public LinkedListBack(int val){
            first = new Node();
            first.val = val;
        }
        public Node first = null;
        public void insert(int i){
            Node n = new Node();
            n.val = i;
            n.next = first;
            first = n;
        }
    }

    private static class Node {
        public Node next = null;
        public int val;
    }

    //max > in[i] > 0
    public static LinkedListBack[] sorted(int[] in, int max){
        LinkedListBack[] ar = new LinkedListBack[max + 1];
        for (int i = 0; i < in.length; i++) {
            int val = in[i];
            if(ar[val] == null){
                ar[val] = new LinkedListBack(val);
            } else {
                ar[val].insert(val);
            }
        }
        return ar;
    }
}

Entonces, ¿esto cuenta como una especie de O (n), a pesar de que devuelve el resultado en un formato funky?

Answer 1

Eso se llama Radix Sort , y sí rompe la barrera nlog (n), que es solo una barrera en el Comparison Model . En la página de wikipedia vinculada para el Modelo de comparación, puede ver una lista de géneros que la usan y algunas que no.

Ordenar radix colocando cada elemento en un cubo, en función de su valor y luego concatenar todos los depósitos juntos de nuevo al final. Solo funciona con tipos como enteros que tienen un número finito de valores posibles.

Normalmente, una ordenación de radix se realiza un byte o un mordisco a la vez para reducir el número de cubetas. Vea el artículo de Wikipedia en él, o busque más información.

Tu también se puede hacer para clasificar números negativos y solo asignar memoria para los cubos que usa para mejorarlo.

Answer 2

Para responder directamente a tu pregunta:

1. Su algoritmo de clasificación técnicamente no es O (n) sino más bien O (n + max), ya que necesita crear una matriz de tamaño máximo, que toma el tiempo O (máximo).
2. Esto no es un problema; de hecho, es un caso especial de un conocido algoritmo de clasificación que rompe la barrera Ω (n log n).

Entonces, ¿qué es esta barrera Ω (n log n)? ¿De dónde viene? ¿Y cómo lo rompes?

La barrera Ω (n log n)

La barrera Ω (n log n) es el límite inferior teórico de la información en la velocidad promedio de cualquier algoritmo de clasificación basado en la comparación . Si las únicas operaciones que se le permite aplicar a los elementos de la matriz para distinguirlas es realizar algún tipo de comparación, entonces su algoritmo de clasificación no puede obtener mejores resultados que Ω (n log n) en el caso promedio.

Para entender por qué ocurre esto, pensemos en el estado del algoritmo en cualquier punto durante su ejecución. A medida que el algoritmo se ejecuta, puede obtener cierta cantidad de información sobre la forma en que se ordenaron los elementos de entrada. Digamos que si el algoritmo tiene algún conjunto de información X sobre el orden original de los elementos de entrada, entonces el algoritmo está en el estado X.

El quid del argumento Ω (n log n) (y varios argumentos relacionados, como veremos más adelante) es que el algoritmo debe tener la capacidad de entrar en un gran número de estados diferentes según la entrada. Supongamos por ahora que la entrada al algoritmo de clasificación es una matriz de n valores distintos. Debido a que el algoritmo no puede decir nada acerca de esos elementos que no sean la forma en que están ordenados, realmente no importa cuáles sean los valores que se están ordenando. Todo lo que importa es el orden relativo de esos n elementos relativos entre sí.

Ahora, para el paso clave, supongamos que hay f (n) formas únicas de ordenar los n elementos de entrada y supongamos que nuestro algoritmo de clasificación no puede entrar en al menos f (n) estados diferentes. Si este es el caso, entonces tiene que haber dos ordenamientos diferentes de los elementos en la matriz que el algoritmo siempre agrupa en el mismo estado. Si esto sucede, entonces el algoritmo de clasificación no puede clasificar correctamente las dos matrices de entrada correctamente. El razonamiento detrás de esto es que debido a que el algoritmo trata las dos matrices de forma idéntica, los pasos que use para reordenar los elementos de la primera matriz serán los mismos que los pasos que utiliza para reordenar los elementos de la segunda matriz. Dado que las dos matrices no son iguales, tiene que haber al menos un elemento que estará fuera de lugar en uno de los dos casos. En consecuencia, sabemos que el algoritmo de clasificación debe ser capaz de entrar en f (n) estados diferentes.

Pero, ¿cómo puede el algoritmo entrar en estos diferentes estados? Bueno, pensemos sobre esto. Inicialmente, el algoritmo no tiene información sobre el orden de los elementos. Cuando hace su primera comparación (por ejemplo, entre los elementos A [i] y A [j]), el algoritmo puede entrar en uno de dos estados: uno donde A [i] <A [j] y otro donde A [i] > A [j]. De manera más general, cada comparación que realiza el algoritmo puede, en el mejor de los casos, ubicar el algoritmo en uno de los dos nuevos estados en función del resultado de la comparación. Por lo tanto, podemos pensar en una gran estructura de árbol binario que describa los estados en los que puede estar el algoritmo: cada estado tiene hasta dos niños que describen en qué estado ingresa el algoritmo en función del resultado de la comparación que se realiza. Si tomamos cualquier camino desde la raíz del árbol hasta una hoja, obtenemos la serie de comparaciones que el algoritmo realiza sobre una entrada en particular. Para ordenar lo más rápido posible, queremos hacer la menor cantidad posible de comparaciones, por lo que queremos que esta estructura de árbol tenga la menor altura posible.

Ahora, sabemos dos cosas. Primero, podemos pensar en todos los estados en los que el algoritmo puede entrar como un árbol binario. Segundo, ese árbol binario debe tener al menos f (n) nodos diferentes en él. Dado esto, el árbol binario más pequeño posible que podamos construir tiene que tener una altura mínima de Ω (log f (n)). Esto significa que si hay f (n) diferentes formas posibles de ordenar los elementos de la matriz, tenemos que hacer al menos Ω (log f (n)) comparaciones en promedio , ya que de lo contrario no podemos entrar en suficientes estados diferentes.

Para concluir la prueba de que no puede vencer Ω (n log n), tenga en cuenta que si la matriz tiene n elementos distintos en ella, entonces hay n! diferentes formas posibles de ordenar los elementos. usando la aproximación de Stirling , tenemos ese log n! = Ω (n log n), y entonces tenemos que hacer al menos comparaciones Ω (n log n) en el caso promedio para ordenar la secuencia de entrada.

Excepciones a la regla

En lo que acabamos de ver arriba, vimos que si tiene n elementos de matriz que son todos distintos, no puede ordenarlos con una clasificación de comparación más rápida que Ω (n log n). Sin embargo, este supuesto inicial no es necesariamente válido. Muchas matrices que nos gustaría ordenar pueden tener elementos duplicados en ellas. Por ejemplo, supongamos que quiero ordenar matrices compuestas únicamente por ceros y unos, como esta matriz aquí:

 0 1 0 1 1 1 0 0 1 1 1

En este caso, no es cierto que haya n! diferentes matrices de ceros y unos de longitud n. De hecho, solo hay 2 ⁿ de ellos. De nuestro resultado anterior, esto significa que deberíamos poder ordenar el tiempo Ω (log 2 ⁿ ) = Ω (n) usando un algoritmo de clasificación puramente basado en la comparación. De hecho, podemos hacer esto absolutamente; Aquí hay un bosquejo de cómo lo haríamos:

1. Mira el primer elemento.
2. Copie todos los elementos menos que el primer elemento en una matriz llamada ''menos''
3. Copia todos los elementos iguales al primer elemento en una matriz llamada ''igual''
4. Copia todos los elementos mayores que el primer elemento en una matriz llamada ''mayor''
5. Concatenar las tres matrices juntas en el orden menor, igual o mayor.

Para ver que esto funciona, si 0 es nuestro primer elemento, entonces la matriz ''menos'' estará vacía, la matriz ''igual'' tendrá todos los ceros, y la matriz ''mayor'' tendrá todos los conjuntos. Concatenándolos, coloca todos los ceros antes que todos. De lo contrario, si 1 es nuestro primer elemento, entonces la matriz less mantendrá los ceros, la matriz equal retendrá los unos, y la matriz más greater estará vacía. Su concatenación es, por lo tanto, todos ceros seguidos por todos, según sea necesario.

En la práctica, no usaría este algoritmo (usaría una clasificación de conteo, como se describe a continuación), pero muestra que efectivamente puede vencer a Ω (n log n) con un algoritmo basado en la comparación si el número de posibles entradas para el algoritmo es pequeño.

Se sabe que algunos algoritmos de clasificación basados ​​en comparación funcionan muy rápidamente en las entradas que tienen múltiples valores duplicados. Por ejemplo, se sabe que Quicksort con un paso especial de particionamiento puede aprovechar los elementos duplicados en la matriz de entrada.

Clases sin comparación

Toda esta discusión ha supuesto que estamos hablando de clasificación basada en la comparación, donde la única operación permitida en los elementos de la matriz es una comparación. Sin embargo, si sabemos más acerca de qué elementos vamos a clasificar y podemos realizar operaciones en esos elementos más allá de simples comparaciones, ninguno de los límites anteriores se mantiene. Estamos rompiendo las suposiciones iniciales que nos llevaron a construir un árbol binario de todos los estados del algoritmo, por lo que no hay razón para sospechar que esos límites se mantendrán.

Por ejemplo, si sabe que los valores de entrada se extraen de un universo que solo tiene | U | elementos en él, entonces puede ordenar el tiempo O (n + | U |) usando un algoritmo inteligente. Comience creando | U | diferentes cubos en los que podemos colocar los elementos de la matriz original. Luego, itere a través de la matriz y distribuya todos los elementos de la matriz en el segmento correspondiente. Finalmente, visite cada uno de los depósitos, comenzando con el cubo que contiene copias del elemento más pequeño y termine con el cubo que contiene copias del elemento más grande, luego concatenar todos los valores que encuentre. Por ejemplo, veamos cómo ordenar matrices que consten de los valores 1 a 5. Si tenemos esta matriz inicial:

1 3 4 5 2 3 2 1 4 3 5

Entonces podemos poner esos elementos en cubos como este:

Bucket     1  2  3  4  5
           -------------
           1  2  3  4  5
           1  2  3  4  5
                 3

Al iterar a través de los cubos y concatenar sus valores juntos se obtiene esto:

1 1 2 2 3 3 3 4 4 5 5

que, por supuesto, es una versión ordenada de nuestra matriz original! El tiempo de ejecución aquí es O (n) tiempo para ir y distribuir los elementos de la matriz original en los cubos, luego O (n + | U |) tiempo para iterar a través de todos los cubos volviendo a juntar los elementos. Tenga en cuenta que si | U | = O (n), esto se ejecuta en el tiempo O (n), rompiendo la barrera de clasificación Ω (n log n).

Si está ordenando enteros, puede hacer mucho mejor que esto usando radix sort , que se ejecuta en O (n lg | U |). Si se trata de int Primitivas, lg | U | generalmente es 32 o 64, así que esto es extremadamente rápido. Si está dispuesto a implementar una estructura de datos particularmente complicada, puede usar un árbol de van Emde Boas para ordenar enteros de 0 a U - 1 en el tiempo O (n lg lg U), explotando el hecho de que los enteros consisten en grupos de bits que pueden ser manipulados en bloques.

Del mismo modo, si sabe que sus elementos son cadenas, puede ordenar rápidamente creando un trie de las cadenas, y luego iterando a través del trie para reconstruir todas las cadenas. Alternativamente, podría considerar las cadenas como números escritos en una base grande (por ejemplo, base 128 para texto ASCII) y luego usar uno de los algoritmos de clasificación enteros de arriba.

En cada uno de estos casos, la razón por la que puede vencer la barrera de la teoría de la información es que está rompiendo la suposición inicial de la barrera, es decir, que solo puede aplicar comparaciones. Si puede tratar los elementos de entrada como números, o como cadenas, o como cualquier otra cosa que revele más estructura, todas las apuestas están desactivadas y puede ordenar de manera extremadamente eficiente.

¡Espero que esto ayude!