Medidas del Orden de una Secuencia

Como complemento al artículo de los Algoritmos de Pseudoordenación creo que sería útil comentar algunas maneras sencillas de medir cuan ordenada está una secuencia.

La idea es relacionar cada una de ellas con un algoritmo de ordenación que se dedique a incrementarla iteración a iteración.

Elementos en su sitio

El número de elementos que están en su posición definitiva es una mala medida de quan ordenada está una secuencia de elementos. Esto es así porque la secuencia (9, 1, 2, 3, 4, 5, 6, 7, 8) está muy ordenada y sin embargo ninguno de sus elementos está en su sitio.

Aún así hay algoritmos de ordenación que se dedican a poner, iteración a iteración, cada elemento en su lugar. El Selectionsort nos asegura i elementos en su posición definitiva en la iteración i mientras que el Quicksort nos asegura 2^i (por eso el primero es un algoritmo O(N²) mientras que el segundo es O(N·log(N)).

Distancia Tau de Kendall

La medida anterior no es conveniente por no detectar el orden de una secuencia como: (9, 1, 2, 3, 4, 5, 6, 7, 8) . Una posible solución a este problema la ofrece la Distancia Tau de Kendall que consiste en comparar la secuencia completamente ordenada con la secuencia cuyo desorden queremos medir. Para ello contamos, para todos los posibles pares de elementos diferentes de la secuencia, cuantos NO tienen la misma posición relativa en la secuencia ordenada y en la que queremos medir:

Por ejemplo: Queremos saber cuan ordenada es la secuencia (2, 4, 1, 3). Para ello la comparamos con la secuencia (1, 2, 3, 4) de la siguiente manera:

  1. Sumamos un punto por cada pareja que invierte su orden en una respecto a la otra:
    • (2,1) + (4,1) + (4,3) = 3
  2. Normalizamos dividiendo por el máximo:
    • 3 / 4*(4-1)/2 = 1/2

Ahora sabemos que esa secuencia está un 50% desordenada. La única secuencia 100% desordenada es (4, 3, 2, 1) cosa que ya tiene cierto sentido.

El algoritmo de Ordenación por Burbuja da tantos pasos como parejas con su orden invertido haya y por lo tanto la Distancia Tau de Kendall sin normalizar se ve reducida en una unidad en cada iteración de el mismo.

Distancia de cada elemento a su posición definitiva

Sumar la distancia de cada elemento a su posición definitiva (y luego normalizar) es en cierta manera equivalente a medir el desorden con la distancia Tau de Kendall. Sin embargo es quizá más interesante quedarnos con el máximo de estas distancias ya que al hacer la media somos incapaces de distinguir entre el caso en el que hay pocos elementos a mucha distancia y el caso en el que hay muchos elementos a poca distancia. Este último caso sí se detecta quedándonos con el máximo de las distancias y resulta ser mucho más útil.

En una secuencia de N elementos elegida al azar cada elemento está, de media, a distancia N/3 de su posición definitiva.

El Quicksort nos asegura que en la iteración i cada elemento está, como mucho, a distancia N/(2^i) de su posición final.

Subsecuencia Creciente de Longitud Máxima

Una Subsecuencia Creciente se puede obtener eliminando elementos de la secuencia original hasta que lo que quede sea una secuencia ordenada. Si nos preocupamos por eliminar el mínimo número de elementos posibles obtendremos la Subsecuencia Creciente de Longitud Máxima.

Si la SCLM de una secuencia es de tamaño N significa que la secuencia está ordenada crecientemente mientras que si es de tamaño 1 está ordenada decrecientemente. En una secuencia de N elementos elegida al azar, el tamaño de la SCLM es, de media, √N.

En la iteración i el Mergesort nos asegura la existencia de una SCLM de tamaño 2^i.

BOLAEXTRA: Este post pertenece a una serie especial de 5 artículos relacionados:
Quick Sort

  1. Eficiencia Algorítmica y Notación Asintótica
  2. Algoritmos de Ordenación
  3. Algoritmos de Ordenación Adaptativos
  4. Algoritmos de Pseudoordenación
  5. Medidas del Orden de una Secuencia

Te recomiendo encarecidamente que leas los 5 en orden ya que cada uno de ellos depende fuertemente de los anteriores.

Escrito en 11/12/09 10:00 por Carlos Luna en las categorías:

Comentarios

Gravatar.com se ha roto

Como ya te comenté, tengo dudas sobre la medida de desorden de una secuencia. Significa que si está más desordenado se tarda más en ordenar? distintos algoritmos de ordenación dan tiempos totalmente distintos con la misma secuencia desordenada siendo en algunos la ordenación inversa la peor causística pero en otros no.
Yo veo más una secuencia más desordenada que otra, como menos información puedes obtener de la secuencia, o más aleatoria es. Yo usaría algo parecido a la autocorrelación de la secuencia con si misma o a la entropía.

metge | 13/12/09 13:04 | #

Deja un Comentario

Quizás quieras usar textile para dar formato a tu comentario.

"linktext":http://       _em_       *strong*       -strike-       ^sup^       ~sub~
bq. Blockquote       # Lista numerada       * Lista no-numerada       ==html crudo, sin textile==

(no será mostrado) (http://...)