Discussion :

[touftouf57]

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]

Personne ne voit une piste?

Je commence à déprimer.

[gorgonite]

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

[Aleph69]

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]

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]

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]

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]

Merci à vous tous,

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.

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.