Complexité de l'algorithme de Tri Fusion

**judge06** · 25/03/2007, 18h34

Salut tout le monde, je voudrais de l'aide pour demontrer mathematiquement en urilisant la resolution des reccurences que la complexité du Tri Fusion est: T(n) = O(nlogn); Merci

**millie** · 25/03/2007, 18h53

ftp://ftp-developpez.com/lapoire/alg...orithmique.pdf

Section 8.4 Approche diviser pour régner (page 78)

Couplé au théorème du 5.3 page 55

**judge06** · 25/03/2007, 19h12

Merci mais je n'arrive pas à m'y connecter:
Délai d'attente dépassé
Le serveur à l'adresse ftp-developpez.com met trop de temps à répondre.

**millie** · 25/03/2007, 19h19

Essaye avec le lien miroir : http://lapoire.developpez.com/algori...orithmique.pdf

Les deux marchent très bien chez moi

**judge06** · 25/03/2007, 19h22

Merci, maintenant j ai pu telecharger le fichier. Je vais y voir de plus pret

**judge06** · 25/03/2007, 19h35

Envoyé par millie

Essaye avec le lien miroir : http://lapoire.developpez.com/algori...orithmique.pdf

Les deux marchent très bien chez moi

Merci, j'y ai vu d'autre methode de tri mais pas celle qui m'interessent: le Tri Fusion

**millie** · 25/03/2007, 19h41

t'as du mal lire à mon avis...

L'algorithme TriRec (8.4.1) c'est le tri fusion. Le 8.4 expose la méthode générale du tri fusion, en choisissant une partition quelconque de l'ensemble. Le 8.4.1 est le cas particulier où l'on coupe le tableau au milieu...

**judge06** · 25/03/2007, 20h11

Oui, vous avez raison! maintenant quand meme je croi que j'ai bien lu mais je ne vois pas comment passer de : f(n) = n + 2f(n/2) et dire qu'on ogtien une complexité nlogn