Mesure du «désordre» d'un tableau

Question

Étant donné un tableau de valeurs, je veux trouver le «score» total, où le score de chaque élément est le nombre d'éléments dont la valeur est inférieure à la précédente dans le tableau.

par exemple.

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

Un algorithme O (n^2) est trivial, mais je soupçonne qu'il peut être possible de le faire en O (NLGN), en triant le tableau. Est-ce que quelqu'un a des idées sur la façon de le faire ou si ce n'est pas possible?

Answer 1

On dirait que ce que vous faites est essentiellement de compter le nombre de paires d'éléments qui sont dans l'ordre relatif incorrect (c'est-à-dire le nombre de inversions). Cela peut être fait dans O (n * log (n)) en utilisant la même idée que le tri par fusion. Au fur et à mesure que vous fusionnez, vous comptez simplement le nombre d'éléments qui sont dans la liste de gauche mais qui auraient dû figurer sur la liste de droite (et vice versa).

Answer 2

Si la plage de vos nombres est assez petite, l'algorithme le plus rapide que je peux penser est celui qui utilise Fenwick Trees. Pour l'essentiel, parcourez simplement la liste et interrogez Fenwick Tree sur le nombre d'éléments qui le précède, puis insérez le nombre dans l'arborescence. Cela répondra à votre question dans O (nlogm), où n est la taille de votre liste et m est votre plus grand entier.

Si vous ne disposez pas d'une fourchette raisonnable sur vos entiers (ou si vous voulez économiser de l'espace) La solution est MAK sacrément élégante, utilisez donc que :)