Calcul du nombre d’inversions

Soit {t} un tableau de taille {n,} et soit {\left\{i,j\right\}} une paire d’indices distincts dans {[\![ 0,n-1]\!] .}

On dit que la paire {\left\{i,j\right\}} représente une inversion (dans le tableau {t)} si on a {i\lt j} et {t_{i}>t_{j}.}

Un moyen na ̈if de compter les inversions d’un tableau est de tester toutes les paires {\left\{i,j\right\}.}

L’algorithme obtenu est alors de complexité {n^{2}.}

La fonction nbinv_naif ci-dessous apporte une solution.

Voici un exemple d’utilisation :

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :