Compter les paires d'inversion

Une application classique de diviser pour mieux régner consiste à résoudre le problème suivant:

Étant donné un tableau d'éléments distincts et comparables, comptez le nombre de paires d'inversion dans le tableau: paires telles que et .$a[1\dots n]$$(i,j)$$a[i] \gt a[j]$$i \lt j$

Une approche consiste à faire un tri par fusion, mais aussi à compter le nombre de paires d'inversion dans les sous-problèmes. Au cours de l'étape de fusion, nous comptons le nombre de paires d'inversion qui s'étendent sur les (deux) sous-problèmes et ajoutons au nombre de sous-problèmes.

Bien que cela soit bon et donne un algorithme de temps , cela perturbe le tableau.$O(n\log n)$

Si nous avons la contrainte supplémentaire que le tableau est en lecture seule, alors nous pouvons faire une copie et traiter la copie, ou utiliser une structure de données supplémentaire comme un arbre binaire équilibré de statistiques de commande pour effectuer le comptage, qui utilisent toutes deux Espace .$\Theta(n)$

La question actuelle est d'essayer d'améliorer l'espace, sans affecter le temps d'exécution. c'est à dire

Existe-t-il un algorithme de temps pour compter le nombre de paires d'inversion, qui fonctionne sur un tableau en lecture seule et utilise un espace sub-linéaire (c'est-à-dire )?$O(n\log n)$$o(n)$

Supposons un modèle de RAM à coût uniforme et que les éléments prennent de l' espace et la comparaison entre eux est .$O(1)$$O(1)$

Une référence fera l'affaire, mais une explication sera meilleure :-)

J'ai essayé de chercher sur le Web, mais je n'ai trouvé aucune réponse positive / négative à cela. Je suppose que c'est juste une curiosité.

Voici la réponse de Raphaël:

$o(n\log n)$$\Omega(n)$$O(n)$$\Omega(n)$