tri & complexité

Bonsoir,

je bloque sur un énoncé, pouvez-vous me débloquer.

1er exo:
Soit A et B 2 tableaux de taille n et contenant des entiers positifs.
Donner un algorithme (le plus éfficace possible) qui vérifie si A et B sont disjoints (c'est à dire ne contenant aucun élément en commun) Evaluer sa compléxité?

voilà ce que j'ai fait:
(je tri les 2 tableaux avec un tri fusion et ensuite je fait une fonction disjoint en O(n) pour dire si les tableaux sont disjoint ou non)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

void fusion(int *tab,int debut,int milieu,int fin){ int tab1[milieu],tab2[fin-milieu],tailleTab2=fin-milieu,posA=0,posB=0,i; for(i=0;i<milieu;i++) tab1[i]=tab[i];   for(i=0;i<tailleTab2;i++) tab2[i]=tab[milieu+i];   for(i=0;(posA<milieu && posB<tailleTab2);i++){ if(tab1[posA]>tab2[posB]) tab[i]=tab2[posB++]; else tab[i]=tab1[posA++]; } for(;posA<milieu;) tab[i++]=tab1[posA++];   for(;posB<tailleTab2;) tab[i++]=tab2[posB++]; }   void triFusion(int *tab,int debut,int fin){ int milieu; if(debut<fin){ milieu=(debut+fin)/2; triFusion(tab,debut,milieu); triFusion(tab,milieu+1,fin); fusion(tab,debut,milieu,fin); } }   int disjoint(int *tab1,int *tab2,int n){ int posA=0,posB=0,save,NTab; triFusion(tab1,1,n); triFusion(tab2,1,n);   for(;(posA<n && posB<n);){ if(tab1[posA]>tab2[posB]){ if((posB || posA) && (tab2[posB]==save) && NTab==1) return 0; save=tab2[posB++]; NTab=2; } else{ if((posB || posA) && (tab1[posA]==save) && NTab==2) return 0; NTab=1; save=tab1[posA++]; } } return 1; }

---

je sais que le trie fusion est en O(n log n) et ma fonction disjoint en O(n)
donc logiquement je serai au final en O(n).

est ce bon?

je doit démontrer cette compléxité mais je n'arrive pas à calculer la compléxité du tri fusion, pouvez-vous m'expliquer comment faire?

2 iéme exo:

Soit A un tableau de n nombres réels positifs et distincts. Supposons que la différence enetre deux nombres quelconques dans A est au moins (1/10^5) et au plus (10^5). Proposer un algorithme en 0(n) pour trier le tableau A.

je trouve pas d'algorithme en 0(n), le seul algo que je trouve qui se raproche est en O(n+MAX), en cherchant le max et un tableau temporaire de taille MAX+1 et après je joue avec les indices du tableau pour trier.

je trouve pas, comment doit je m'y prendre?

merci d'avance pour votre aide.

Salut.

Personnellement, pour le n°1, j'aurais tout simplement fait un truc du genre :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

# include <stdio.h> # define size1 5 # define size2 7   int main (void) { int var=1, i, j; int t1 [size1] = {8,5,0,2,1}; int t2 [size2] = {10,23,78,9,21,100,31}; /* Les itérations se stoppent à partir du moment où il y a une valeur commune   ou bien lorsque la fin de t1 est atteinte */ for (i=0 ; var == 1 && i<size1 ; i++) { for (j=0; j<size2 && var == 1; j++) { if (t2[j] == t1[i]) var=0; } } if (var == 1) printf ("disjoints\n"); else printf ("pas disjoints\n"); return 0; }

---

C'est sûr que si les éléments était triés en ordre croissant ou décroissant, tu aurais moins d'itérations ... mais, le tri à lui seul engendrerait un certain nombre d'itérations. En bref, je ne suis pas sûr que tu aurais un gain de temps à ordonner les tableaux, je me trompe ?

Citation:

---

Envoyé par Delnir

Bonsoir,

je bloque sur un énoncé, pouvez-vous me débloquer.

1er exo:
Soit A et B 2 tableaux de taille n et contenant des entiers positifs.
Donner un algorithme (le plus éfficace possible) qui vérifie si A et B sont disjoints (c'est à dire ne contenant aucun élément en commun) Evaluer sa compléxité?

voilà ce que j'ai fait:
(je tri les 2 tableaux avec un tri fusion et ensuite je fait une fonction disjoint en O(n) pour dire si les tableaux sont disjoint ou non)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

void fusion(int *tab,int debut,int milieu,int fin){ int tab1[milieu],tab2[fin-milieu],tailleTab2=fin-milieu,posA=0,posB=0,i; for(i=0;i<milieu;i++) tab1[i]=tab[i];   for(i=0;i<tailleTab2;i++) tab2[i]=tab[milieu+i];   for(i=0;(posA<milieu && posB<tailleTab2);i++){ if(tab1[posA]>tab2[posB]) tab[i]=tab2[posB++]; else tab[i]=tab1[posA++]; } for(;posA<milieu;) tab[i++]=tab1[posA++];   for(;posB<tailleTab2;) tab[i++]=tab2[posB++]; }   void triFusion(int *tab,int debut,int fin){ int milieu; if(debut<fin){ milieu=(debut+fin)/2; triFusion(tab,debut,milieu); triFusion(tab,milieu+1,fin); fusion(tab,debut,milieu,fin); } }   int disjoint(int *tab1,int *tab2,int n){ int posA=0,posB=0,save,NTab; triFusion(tab1,1,n); triFusion(tab2,1,n);   for(;(posA<n && posB<n);){ if(tab1[posA]>tab2[posB]){ if((posB || posA) && (tab2[posB]==save) && NTab==1) return 0; save=tab2[posB++]; NTab=2; } else{ if((posB || posA) && (tab1[posA]==save) && NTab==2) return 0; NTab=1; save=tab1[posA++]; } } return 1; }

---

je sais que le trie fusion est en O(n log n) et ma fonction disjoint en O(n)
donc logiquement je serai au final en O(n).

est ce bon?

---

Ben non. Tu cumules deux actions qui ont des complexités différentes, ta complexité finale sera égale à la plus complexe des deux actions => nlog(n)

Accessoirement, je trouve ta fonction "disjoint" assez lourde. Pourquoi ne pas la programmer comme un appareillage ? Tu lis au départ le premier élément de chaque tableau puis ensuite tu ne lis que le tableau qui a son élément inférieur à l'élément en cours sur l'autre tableau. Et dès qu'il devient supérieur, tu bascules sur l'autre tableau etc...

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

int disjoint(int *tab1,int *tab2,int n){ int posA=-1, flagA=1, posB=-1, flagB=1; triFusion(tab1,1,n); triFusion(tab2,1,n);   while (1) { if (flagA) { posA+=1; if (posA == n) break; flagA=0; }   if (flagB) { posB+=1; if (posB == n) break; flagB=0; }   if (tab1[posA] == tab2[posB]) return 1;   if (tab1[posA] < tab2[posB]) flagA=1;   if (tab2[posB] < tab1[posA]) flagB=1; } return 0; }

---

L'avantage de cet algo tel qu'il est écrit est qu'il peut rapidement être adapté à 3, 4, 5 tableaux ou même plus. On peut même adapter l'algo pour évaluer "n" tableaux (n étant passé en paramètre)..

Citation:

---

Envoyé par Delnir

2 iéme exo:

Soit A un tableau de n nombres réels positifs et distincts. Supposons que la différence enetre deux nombres quelconques dans A est au moins (1/10^5) et au plus (10^5). Proposer un algorithme en 0(n) pour trier le tableau A.

---

Hum, je vois pas trop. Essaye de poster ton problème dans la section "algo"...

Merci pour votre aide,
pour te répondre ok.Idriss je cherche l'algorithme le plus éfficace possible (pour mon niveau actuel de programmation), hors ton algorithme dans le pire des cas sera en O(n^2).
Pour le moment j'ai trouvé quelque chose en O(n log n) comme ma dit Sve@r,
enfin pour être plus précis sa serai plutôt si n<10 O(n) et si n >=10 O(n log n)
j'ai tord?

je vais poster dans la section algoithmique comme tu me la conseillé