Inversion dans un tableau
Bonjour,
Est ce que quelqu'un aurait une idee d'algorithme en O(nlog(n)) pour compter le nombre d'inversion dans un tableau de n elements.
PS : une inversion c qd i<j et A[i]>A[j]
Est ce que quelqu'un aurait une idee d'algorithme en O(nlog(n)) pour compter le nombre d'inversion dans un tableau de n elements.
PS : une inversion c qd i<j et A[i]>A[j]
Configuration: Windows Vista Firefox 3.0.4
3 réponses
-
ModérateurSalut,
Effectivement j'aurais bien une idée, qui suivrait un peu la philosophie de la recherche dichotomique ou du tri dichotomique...
C'est un exo que tu dois faire? -
votre question n'est pas claire
pour cherche le nombre des inversions possible d'un tableau (l'algorithme)
il faut définire exactement qui ce que c'est une inversion -
si le sens de votre question est le suivant :
par exemple :
SI T = 4, 5, 3, 1
on a :
4>3
4>1
5>3
5>1
3>1
donc :
le nombre des inversion est 5
et l'algorithme est la suivante :
nb-inversion =0
pour i =1 à taille-T faire
pour j = i+1 à taille-T faire
si T(i)>T(j)
nb-inversion =nb-inversion+1
fin si
fin pour
fin pou
c'est simple.......
reponder moi
