arrays - sheet - time complexity

calcular el número de “inversiones” en una permutación

Question

Sea A una matriz de tamaño N llamamos a un par de índices (i,j) un "inverso" si i < j y A[i] > A[j]

Necesito encontrar un algoritmo que reciba una matriz de tamaño N (con números únicos) y devolver el número de inversos en el tiempo de O(n*log(n)) .

Answer 1

Creo que la mejor manera de hacer esto (y eso es solo porque me encanta la estructura de datos) es usar un árbol indexado binario . Tenga en cuenta que, si todo lo que necesita es una solución, la ordenación por fusión funcionaría igual de bien (¡solo creo que este concepto es totalmente increíble!). La idea básica es la siguiente: cree una estructura de datos que actualice los valores en O (registro n) y responda a la consulta "¿Cuántos números menos que x ya han ocurrido en la matriz hasta ahora?" Dado esto, puede responder fácilmente cuántos son mayores que x, lo que contribuye a las inversiones con x como el segundo número en el par. Por ejemplo, considere la lista {3, 4, 1, 2}.

Al procesar 3, no hay otros números hasta el momento, por lo que las inversiones con 3 en el lado derecho = 0 Al procesar 4, el número de números menores que 4 hasta ahora = 1, por lo tanto, el número de números mayores (y, por lo tanto, las inversiones) = 0 Ahora , al procesar 1, número de números menores que 1 = 0, este número de números mayores = 2 que contribuye a dos inversiones (3,1) y (4,1). La misma lógica se aplica a 2, que encuentra 1 número menor que él y, por lo tanto, 2 mayor que él.

Ahora, la única pregunta es entender cómo ocurren estas actualizaciones y consultas en el registro n. El url mencionado anteriormente es uno de los mejores tutoriales que he leído sobre el tema.

Answer 2

Estos son los algoritmos MERGE y MERGE-SORT originales de Cormen, Leiserson, Rivest, Stein Introducción a los algoritmos:

MERGE(A,p,q,r)
 1  n1 = q - p + 1
 2  n2 = r - q
 3  let L[1..n1 + 1] and R[1..n2 + 1] be new arrays
 4  for i = 1 to n1
 5      L[i] = A[p + i - 1]
 6  for j = 1 to n2
 7      R[j] = A[q + j]
 8  L[n1 + 1] = infinity
 9  R[n2 + 1] = infinity
10  i = 1
11  j = 1
12  for k = p to r
13      if L[i] <= R[j] 
14          A[k] = L[i]
15          i = i + 1
16      else A[k] = R[j]
17          j = j + 1

y

MERGE-SORT(A,p,r)
 1 if p < r
 2     q = floor((p + r)/2)
 3     MERGE-SORT(A,p,q)
 4     MERGE-SORT(A,q + 1,r)
 5     MERGE(A,p,q,r)

en la línea 8 y 9 en MERGE, el infinito es la llamada tarjeta centinela, que tiene tal valor que todos los elementos de la matriz son más pequeños que ella. Para obtener el número de inversión se puede introducir un contador global, digamos que ninv se inicializa a cero antes de llamar a MERGE-SORT y luego se modifica el algoritmo MERGE agregando una línea en la instrucción else después de la línea 16, algo como

ninv += n1 - i

después de que finalice MERGE-SORT, ninv mantendrá el número de inversiones

Answer 3

Hay un artículo publicado en SIAM en 2010 por Cham y Patrascu, titulado Conteo de inversiones, Conteo de rango ortogonal fuera de línea, y Problemas relacionados que le da un algoritmo que toma tiempo O (n sqrt (log (n))). Este es actualmente el mejor algoritmo conocido y mejora el algoritmo O (n log (n) / log (log (n))) de larga data. De lo abstracto:

Damos un algoritmo de tiempo O (n sqrt (lg n)) para contar el número de inversiones en una permutación en n elementos. Esto mejora un límite anterior de larga data de O (n lg n / lg lg n) que siguió a la estructura de datos de Dietz [WADS''89], y responde a una pregunta de Andersson y Petersson [SODA''95]. Como se sabe que el resultado de Dietz es óptimo para el problema de rango dinámico relacionado, nuestro resultado demuestra una mejora significativa en la configuración fuera de línea .

Nuestra nueva técnica es bastante simple: realizamos una "partición vertical" de un trie (similar a los árboles de van Emde Boas), y usamos ideas de la memoria externa. Sin embargo, la técnica encuentra numerosas aplicaciones: por ejemplo, obtenemos

• en d dimensiones, un algoritmo para responder n consultas de conteo de rango ortogonal fuera de línea en el tiempo O (n lg ^{d-2 + 1 / d} n) ;
• un tiempo de construcción mejorado para las estructuras de datos en línea para el conteo de rango ortogonal;
• un tiempo de actualización mejorado para el problema de las sumas parciales;
• Los algoritmos de RAM de palabra más rápidos para encontrar la profundidad máxima en una disposición de rectángulos alineados con el eje, y para el problema de selección de pendiente.

Como beneficio adicional, también proporcionamos un algoritmo de aproximación simple (1 + ε) para contar inversiones que se ejecuta en tiempo lineal, mejorando el límite O (n lg lg n) anterior de Andersson y Petersson.

Answer 4

Puede utilizar el algoritmo de ordenamiento de mezcla .

En el bucle del algoritmo de fusión, las mitades izquierda y derecha están ordenadas ascendentemente, y queremos fusionarlas en una sola matriz ordenada. Tenga en cuenta que todos los elementos en el lado derecho tienen índices más altos que aquellos en el lado izquierdo.

Supongamos matriz [leftIndex]> array [rightIndex] . Esto significa que todos los elementos en la parte izquierda que siguen al elemento con índice leftIndex también son más grandes que el actual en el lado derecho (porque el lado izquierdo está ordenado en forma ascendente). Así que el elemento actual en el lado derecho genera las inversiones numberOfElementsInTheLeftSide - leftIndex + 1 , así que agregue esto a su cuenta de inversión global.

Una vez que el algoritmo termine de ejecutarse, tendrá su respuesta, y la clasificación de fusión es O (n log n) en el peor de los casos.