Classement optimal d'une liste chaînée

Fermé

smain123 - 16 déc. 2006 à 12:12
mamiemando Messages postés 33654 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 4 mai 2025 - 16 déc. 2006 à 12:26

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 ecace 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

A voir également:

Classement optimal d'une liste chaînée
Liste déroulante excel - Guide
Liste déroulante en cascade - Guide
Liste site streaming illégal - Accueil - Services en ligne
Liste code ascii - Guide
Liste groupe whatsapp - Guide

1 réponse

Réponse 1 / 1

mamiemando Messages postés 33654 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 4 mai 2025 7 847
16 déc. 2006 à 12:26

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

Discussions similaires

Rechercher un numéro sur liste rouge

Que signifient les abréviations ''bp'', '''bc'', ''db'' etc. au football ?