Classement optimal d'une liste chaînée Fermé

Question

bonjour
j'ai un probleme d'un algrorithme parallelle  le voila
Soit une liste chaînée chaînée L contenant n objets. L'algorithme EREW de classement
par sauts de pointeurs vu en cours est ecace mais non optimal.
Donner un algorithme ClassementListe(L) optimal, de complexité en temps T(n) =
O(log(n)) et utilisant O(n/ log(n)) processeurs comme suit.
i) Réduire la liste L à une liste L0 de taille O(n/ log(n)).
1
ii) Utiliser l'algorithme habituel de classement sur la liste réduite L0, puis récupérer
les objets  ôtés  lors de l'initialisation et calculer leur rang. Quel est le travail
obtenu ? En déduire que ClassementListe(L) est bien optimal.
iii) Quelles hypothèses faut-il formuler sur les entrées de ClassementListe(L) pour oépré
merci de répondre a mon msg au plus vite posible

mamiemando · Answer

Grosso modo tu dois faire ce qui existe actuellement dans les std::set de la STL (cf C++) c'est à dire une structure d'arbre binaire, ou à chaque noeud de l'arbre tu évalues si l'élément à insérer (ou auquel accéder) est plus petit ou plus grand. Ainsi tu divises par deux la zone de recherche à chaque noeud de l'arbre ce qui correspond à du O(log(n)).

http://brassens.upmf-grenoble.fr/IMSS/dciss/Enseignements/PSR/Prog/Java/CoursJava/arbresRougeNoir.htm

Bonne chance

Classement optimal d'une liste chaînée

1 réponse

Discussions similaires