Diviser Pour Régner

**touftouf57** · 31/10/2011, 14h03

Bonjour a tous,

J'ai prochainement un exam d'algo. Je me suis procuré le sujet de l'an dernier. Mais j'ai un exo sur la stratégie "Diviser Pour Régner" qui me pose un sérieux souci.
Voici l'énoncé:

Soit une séquence de nombres entiers positifs S=<s1,s2,s3,...,sn> où on suppose que tous les si sont différents 2 à 2. On dit qu'une paire (i,j) est une inversion de S si i<j et que si>sj.

Exemple: La séquence S <2,6,3,1,5> a 5 inversions: (1,4), (2,3), (2,4) ,(2,5) et (3,4).

a) Donnez un algorithme naïf pour déterminer le nombre d'inversions d'une séquence S. Son temps d’exécution est O(n^2)
b)Donnez un algorithme qui utilise la stratégie Diviser Pour Régner pour déterminer le nombre d'inversion d'une séquence S.

Donc pour la question a) aucun problème, j'utilise une double boucle du style:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
Pour i = 1 à S.length-1{
   Pour j = i à S.Length{
      ...
   next j}
next i}

Temps d’exécution O(n^2)

Maintenant pour la question b) c'est la que cela se complique.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
INVERSION (S,i,j){
si(i=j){
   retourner vide   //pas d'inversion
}sinon{
   k=(i+j)/2
   TabInversion = vide
   G=INVERSION(S,i,k)
   D=INVERSION(S,k+1,j)
TabInversion = G U D  //Je concatène les Inversions des 2 sous-problèmes
   /*Ici il faut que je gère le cas dit "à cheval"
    *Mais je ne vois pas du tout comment le faire sans obtenir un temps d'execution en O(n^2)
   * J'ai tenté de m'inspirer du tri-fusion (O(n log n)) mais cela ne fonctionne pas, vu que j'obtiens 2 sous-ensembles triés, certaines inversions sont annulées
   */
fsi}

Donc est-ce que quelqu'un verrait-il une solution réalisable en un temps < à O(n^2)?

Merci d'avance

**touftouf57** · 31/10/2011, 20h06

Personne ne voit une piste?

Je commence à déprimer.

**gorgonite** · 31/10/2011, 20h33

en gros, tu compares le tri par sélection et le tri rapide...

**Aleph69** · 01/11/2011, 00h21

Bonsoir,

pourquoi veux-tu que la complexité de la stratégie divide&conquer soit inférieure à la stratégie séquentielle? L'idée ici est surtout de diviser le problème initial en plusieurs sous-problèmes pouvant être résolus en parallèle. Pour chaque sous-problème, la complexité sera toujours en O(n^2), mais le n sera d'autant plus petit que tu auras de sous-problèmes, et il y aura un coût de communication qui va venir s'ajouter pour les échanges de données entre processeurs.

**zamato** · 01/11/2011, 00h25

Salut.

Déjà je trouve bizarre que ta fonction INVERSION renvoie un ensemble et non pas un entier, en effet tu cherches le nombre d'inversions.

Il suffit juste de modifier le tri-fusion, au lieu de ne rien renvoyer il renvoie le nombre d'inversion d'un tableau.

Le nombre d'inversion d'un tableau vaut :
1)0 si il y a 1 ou 0 éléments
2)sinon, c'est la somme entre : le nombre d'inversion du tableau de gauche, le nombre d'inversions du tableau de droite, et le nombre d'inversions à cheval sur les deux.

Dans le cas 2), les deux premiers termes se calculent de façon récursive, c'est trivial. La seule difficulté est de trouver le nombre d'inversion à cheval sur les deux sous-tableaux déjà triés (ça se fait pendant le processus de fusion). Mais d'après ton message tu sais déjà le faire.

La complexité est bien sûr O(NlogN) étant donné que c'est un tri fusion légèrement modifié.

**pseudocode** · 01/11/2011, 01h10

Envoyé par zamato

La seule difficulté est de trouver le nombre d'inversion à cheval sur les deux sous-tableaux déjà triés (ça se fait pendant le processus de fusion). Mais d'après ton message tu sais déjà le faire.

La complexité est bien sûr O(NlogN) étant donné que c'est un tri fusion légèrement modifié.

Je ne vois pas trop comment faire la dernière fusion sans devoir comparer 2 à 2 les éléments des deux sous-listes (de taille N/2) --> O(N²).

Je rejoins l'avis d'Aleph69 : l'exo porte sur la méthode D&C, et pas sur la réduction de la complexité.

**zamato** · 01/11/2011, 01h26

Si si, de toute façon dès qu'on parle de diviser pour mieux régner, on tape en général dans dans du nlog n, non?
Edit : Je viens de penser au problème de recherche du min et du max dans un tableau, avec D&C on améliore pas la complexité, mais on a quand même un meilleur facteur.

La fusion des deux tableaux, qui sont triés je le rappelle, se fait en O(n).

Si j'appelle tableau de droite, tableau de gauche, et tableau final les deux sous-tableaux et leur fusion :
Pour chaque élément du tableau de droite, on calcule le nombre d'éléments du tableau de gauche qui seront à sa gauche dans le tableau final.

La somme de tout ça est le nombre d'inversion à cheval sur les deux sous-tableaux.

**touftouf57** · 01/11/2011, 01h40

Merci à vous tous,

Envoyé par pseudocode

Je ne vois pas trop comment faire la dernière fusion sans devoir comparer 2 à 2 les éléments des deux sous-listes (de taille N/2) --> O(N²).

C'est justement ce que je me demandais. Est-il possible de le faire en un temps d’exécution inférieur à O(N²). Donc apparemment il n'y a pas mieux.

Envoyé par Zamato

Pour chaque élément du tableau de droite, on calcule le nombre d'éléments du tableau de gauche qui seront à sa gauche dans le tableau final.

Mais Zamato, pour chaque élément du tableau de droite tu vas réaliser un parcours du tableau gauche pour savoir s'il ne devrait pas être de l'autre coté, non?
Donc le parcours du tableau de droite O(n) et pour chaque élément tu fais un parcours du tableau de gauche O(n) imbriqué. On obtient bien du O(N²).

Maintenant si tu me sors un algo qui réalise la tache demandée en une complexité inférieure à O(N²), je prends volontiers.

**zamato** · 01/11/2011, 02h23

Mais Zamato, pour chaque élément du tableau de droite tu vas réaliser un parcours du tableau gauche pour savoir s'il ne devrait pas être de l'autre coté, non?

Ben justement, on peut le faire un temps constant, quel intérêt de travailler sur deux tableaux triés sinon??

Lors de la fusion, à chaque étape, on insère dans le tableau final soit un élément de gauche soit un élément de droite (le plus petit des deux en fait, car on fait un tri croissant ici). On le fait en maintenant un compteur pour chacun des tableaux. (Si tu ne vois pas ce que je veux dire, il faut revoir le tri-fusion).

Dans le cas ou j'insère un élément du tableau de droite, je connais donc le nombre d'éléments qu'il me reste à insérer dans le tableau de gauche.

**pseudocode** · 01/11/2011, 11h48

Envoyé par zamato

La fusion des deux tableaux, qui sont triés je le rappelle, se fait en O(n).

Si j'appelle tableau de droite, tableau de gauche, et tableau final les deux sous-tableaux et leur fusion :
Pour chaque élément du tableau de droite, on calcule le nombre d'éléments du tableau de gauche qui seront à sa gauche dans le tableau final.

La somme de tout ça est le nombre d'inversion à cheval sur les deux sous-tableaux.

Ah, tu fais réellement le tri du tableau. Je pensais que tu ne faisais que le parcourir, sans toucher aux éléments.

Effectivement, dans ce cas ca fonctionne.

@zamato : Au moment de la fusions, tu n'as pas besoin de parcourir la 2ème sous-liste. En effet, si tu insères un élement 'K' de la liste de droite, ca veut dire que tous les éléments restant de la liste gauche sont supérieurs à 'K'. Et donc il suffit d'augmenter le compteur d'inversion avec la taille restante de la liste gauche.

135 0246   -> {}
135  246   -> {0}             --> +3 
 35  246   -> {0,1}            
 35   46   -> {0,1,2}         --> +2
  5   46   -> {0,1,2,3}
  5    6   -> {0,1,2,3,4}     --> +1 
  _    6   -> {0,1,2,3,4,5}
  _    _   -> {0,1,2,3,4,5,6} --> +0

Total : 6 inversions

**touftouf57** · 01/11/2011, 12h03

Merci, c'est exactement ce que je me suis dit ce matin.
J'ai écrit un algo très ressemblant à ce que Pseudocode a mentionné.
Et bien entendu ça fonctionne.

Merci à tous pour votre aide.

**zamato** · 01/11/2011, 13h19

@zamato : Au moment de la fusions, tu n'as pas besoin de parcourir la 2ème sous-liste. En effet, si tu insères un élement 'K' de la liste de droite, ca veut dire que tous les éléments restant de la liste gauche sont supérieurs à 'K'. Et donc il suffit d'augmenter le compteur d'inversion avec la taille restante de la liste gauche.

N'est-ce pas exactement ce que je décris dans mon post juste au-dessus?