Medición de cómo "fuera de orden" una matriz es

Question

Dada una matriz de valores, quiero encontrar la "puntuación" total, donde la puntuación de cada elemento es la cantidad de elementos con un valor menor que se producen antes en el conjunto.

p. Ej.

values: 4 1 3 2 5 
scores: 0 0 1 1 4 
total score: 6 

Un O (n^2) algoritmo es trivial, pero sospecho que puede ser posible hacerlo en O (NLGN), por la clasificación de la matriz. ¿Alguien tiene alguna idea de cómo hacer eso, o si no es posible?

Answer 1

Parece que lo que está haciendo es, básicamente, contar el número de pares de elementos que están en el orden relativo incorrecto (es decir, el número de inversiones). Esto se puede hacer en O (n * log (n)) usando la misma idea que merge sort. A medida que se fusiona, solo cuenta el número de elementos que están en la lista de la izquierda, pero debería haber estado en la lista de la derecha (y viceversa).

Answer 2

Si el rango de sus números es lo suficientemente pequeño, el algoritmo más rápido que puedo pensar es uno que usa Fenwick Trees. Esencialmente solo itere a través de la lista y consulte el Fenwick Tree para saber cuántos elementos tiene antes, luego inserte el número en el árbol. Esto responderá a su pregunta en O (nlogm), donde n es el tamaño de su lista ym es el número entero más grande.

Si usted no tiene un rango razonable en sus números enteros (o si desea ahorrar espacio) La solución de MAK es muy muy elegante, por lo que utiliza :)