Discussion :

[TabrisLeFol]

Bonjour,
Il s'agit de quelque chose d'assez basique mais j'aimerais que quelqu'un me confirme que c'est bon, ou pas...
Une recherche de max peut se faire iterativement ( theta(n) ) mais j'ai aussi trouvé un algo recursif se basant sur le fait que le max final est le max des max des demi-tableaux... Cette methode ne me semble pas plus rapide, je pense qu'elle est aussi en theta(n). Cependant elle serait avantagé si jamais le calcul des max des demi-tableaux peut se faire en parallèle... Non?

[khayyam90]

Bonjour,
Il s'agit de quelque chose d'assez basique mais j'aimerais que quelqu'un me confirme que c'est bon, ou pas...
Une recherche de max peut se faire iterativement ( theta(n) ) mais j'ai aussi trouvé un algo recursif se basant sur le fait que le max final est le max des max des demi-tableaux... Cette methode ne me semble pas plus rapide, je pense qu'elle est aussi en theta(n). Cependant elle serait avantagé si jamais le calcul des max des demi-tableaux peut se faire en parallèle... Non?

bien le bonjour,

l'algo récursif dont tu parles est aussi en theta(n). Tous les éléments du tableaux devront être accédés pour une simple comparaison.
Mais attention, cet algo ajoute ln_2(n) appels récursifs. Il ne peut donc qu'être plus lent qu'un parcours itératif.
Si tu veux vraiment faire du parallèle, une solution peut être de couper ton tableau et d'en donner une partie à chaque élément parallèle. Chaque élément aura donc à faire un parcours itératif d'une partie du tableau.
Puis tu regroupes tous les sous-max et tu trouves le max.

Dans cette histoire, la récursivité n'apporte rien.

[fearyourself]

Cependant elle serait avantagé si jamais le calcul des max des demi-tableaux peut se faire en parallèle... Non?

Et si le temps de communication est négligeable par rapport aux calculs...

Jc

[TabrisLeFol]

ok, merci.

Et merci d'avoir supprimer les autres posts.