Tri fusion : complexité du découpage

Salut,
Je ne comprend pas pourquoi la partie découpage(uniquement) dans le tri de fusion a une complexité O(log(n)) et non pas O(n),
par exemple si on veut trié un tableau de n=8 alors on doit faire 7 opérations de découpage :

Pièce jointe 293721

pour trié un tableau de 100 éléments on doit faire 100 opérations,ce qui doit normalement correspondre a O(n) non?

dans le cas de l'algorithme de dichotomie on a aussi une complexité log(n) ce qui est compréhensible car pour trouvé un élément dans une liste trié on effectue k opérations avec n=2^k
par exemple pour n=8 on peut trouvé l’élément dans max 3 opérations,par exemple trouvé la valeur 1 :

Pièce jointe 293724

pour un n=100 on effectue 6 opérations

-alors voila pourquoi les 2 algorithmes on la mème complexité log(n) alors que dans le cas de l'algorithme de dichotomie on effectue uniquement k opérations pour trouvé l’élément alors que dans le cas du découpage du tri de fusion on effectue 2^k opérations?

Toute aide est la bienvenu,Merci

Citation:

---

Envoyé par fil1990

Je ne comprend pas pourquoi la partie découpage(uniquement) dans le tri de fusion a une complexité O(log(n)) et non pas O(n),

---

La partie "découpage" a une complexité nulle car il n'y a aucune opération réalisée (aucun traitement sur les données).
D'ailleurs les 4 premières lignes de ton exemple montrent les mêmes données dans le même ordre, la seule différence étant l'espace entre les cases.

Cette partie est utile seulement pour expliquer comment l'algorithme fonctionne. Pour être précis, elle explique qu'on va considérer les données comme les feuilles d'un arbre et pas comme une liste à accès séquentielle.

Code:

---

1 2 3 4

int[8] L = { 3 , 4 , 6 , 2 , 5 , 1 , 8 , 7 } int[2][4] L = {{ 3 , 4 , 6 , 2 },{ 5 , 1 , 8 , 7 }} int[2][2][2] L = {{{ 3 , 4 },{ 6 , 2 }},{{ 5 , 1 },{ 8 , 7 }}} int[2][2][2][1] L = {{{{3},{4}},{{6},{2}}},{{{5},{1}},{{8},{7}}}}

---

Ce que tu nommes le "découpage" a effectivement une complexité en O(n). Il faut lire tous les éléments pour les individualiser (phase de la descente de l'algo récursif). Cette opération n'a absolument aucun rapport avec la recherche dichotomique.
Ce qui prend O(n.log(n)), c'est l'étape de fusion (phase de remontée de l'algo récursif).
O(n + n.log(n) = O(n.log(n)).
On néglige le plus petit terme, n, au profit du plus grand n.log(n). D'où la complexité finale du tri fusion en O(n.log(n)).

Citation:

---

Envoyé par yahiko

Ce que tu nommes le "découpage" a effectivement une complexité en O(n). Il faut lire tous les éléments pour les individualiser (phase de la descente de l'algo récursif). Cette opération n'a absolument aucun rapport avec la recherche dichotomique.
Ce qui prend O(n.log(n)), c'est l'étape de fusion (phase de remontée de l'algo récursif).
O(n + n.log(n) = O(n.log(n)).
On néglige le plus petit terme, n, au profit du plus grand n.log(n). D'où la complexité finale du tri fusion en O(n.log(n)).

---

Merci pour votre réponse,c'est ce que je pensait moi aussi,enfaîte ce qui ma perturbé c'est un cours en ligne,voici ce qu'il dit :

"Quand est-ce que la phase de découpage s'arrête ? Quand on est arrivé à des tableaux de taille 1. Et combien de fois faut-il diviser N par 2 pour obtenir 1 ? On l'a déjà vu, c'est la fonction logarithme ! En effet, si on a un tableau de taille 1, on renvoie le tableau en une seule opération (f(0) = 1), et si on double la taille du tableau il faut faire une découpe de plus (f(2*N) = f(N) + 1). C'est bien notre sympathique fonction du chapitre précédent. On a donc log(N) phases de "découpe" successives."

Moralité : ne pas croire sur parole tout ce qu'on trouve sur le net ;)

Citation:

---

Envoyé par fil1990

Merci pour votre réponse,c'est ce que je pensait moi aussi,enfaîte ce qui ma perturbé c'est un cours en ligne,voici ce qu'il dit :

"Quand est-ce que la phase de découpage s'arrête ? Quand on est arrivé à des tableaux de taille 1. Et combien de fois faut-il diviser N par 2 pour obtenir 1 ? On l'a déjà vu, c'est la fonction logarithme ! En effet, si on a un tableau de taille 1, on renvoie le tableau en une seule opération (f(0) = 1), et si on double la taille du tableau il faut faire une découpe de plus (f(2*N) = f(N) + 1). C'est bien notre sympathique fonction du chapitre précédent. On a donc log(N) phases de "découpe" successives."

---

Tu as log(N) phases de fusions successives (4 dernières lignes dans ton image). Chaque fusion nécessite de traiter les N éléments (= la totalité de la ligne).

Plus formellement, la complexité pour trier une liste de taille n est égale à la complexité pour trier la demi-liste de gauche, plus la complexité pour trier la demi-liste de droite, plus la complexité pour fusionner les deux demi-listes:

C(n) = C(n/2) + C(n/2) + n = 2*C(n/2) + n

En partant d'une liste initiale de taille n=2^p, on trouve le terme général:

C(n) = C(2^p) = 2*C(2^(p-1)) + n = 4*C(2^(p-2)) + 2*n = 8*C(2^(p-3)) + 3*n = ... = (2^p)*C(1) + p*n

La complexité pour trier une liste d'un seul élément est de 0 (rien a faire): C(1)=0

C(n) = (2^p)*0 + p*n = p*n =log₂(n)*n --> O( n*log(n) )

Citation:

---

Envoyé par pseudocode

Tu as log(N) phases de fusions successives (4 dernières lignes dans ton image). Chaque fusion nécessite de traiter les N éléments (= la totalité de la ligne).

---

J'ai 3 phases de fusion(2^3 = 8),chaque phase nécessite de traiter n éléments
donc n*3 éléments a traiter,ce qui veut dire n*log(n)
Sa devrait s'appliquer aussi dans la partie découpage non?,car chaque phase de découpage nécessite de parcourir le tableau et mettre ses valeurs dans les 2 tableaux(gauche,droite),
par exemple dans la 1er phase on parcours le tableau initiale et on place ses valeurs dans les 2 tableaux crée,la 2eme phase on parcours les 2 tableaux (n/2)*2,et ainsi de suite....

voila mon code :

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

size_tab* tri_fusion(int tab[],int n) { size_tab* st=new size_tab[1]; st->taille=n; if(n==1) { st->tab=tab; } else{ int mg=floor(n/2); int md=n-mg; int g[mg],d[md]; remplir(tab,g,0,mg); //remplie le tableau gauche remplir(tab,d,mg,n); size_tab* st_g=tri_fusion(g,mg); size_tab* st_d=tri_fusion(d,md); delete[] g; delete[] d; st->tab= fusion(st_g,st_d); delete[] st_g; delete[] st_d; } return st; }

---

Techniquement parlant, tu n'as pas besoin de créer et remplir les sous-tableaux intermédiaires.
Les appels récursifs peuvent se limiter à indiquer la portion du tableau original sur laquelle l'algo doit opérer.

Seule l'étape de fusion nécessite un sous-tableau temporaire qui est alors recopié dans le tableau original.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

int[] tab= {3,4,6,2,5,1,8,7}; mergesort(tab,0,8);   void mergesort(int[] tab,int offset, int len) { if (len<=1) return;   int halflen=len/2; mergesort(tab, offset, halflen); mergesort(tab, offset+halflen,len-halflen);   int[] merged = new int[len]; int i=offset, imax=offset+halflen, j=imax, jmax=offset+len, k=0; while(i<imax && j<jmax) merged[k++]=(tab[i]<=tab[j])?tab[i++]:tab[j++]; while(i<imax) merged[k++]=tab[i++]; while(j<jmax) merged[k++]=tab[j++];   for(k=0;k<len;k++) tab[offset+k]=merged[k]; }

---