Discussion :

[charlebakhtovsky3]

Bonjour,

Lorsqu'on a deux listes d'éléments non triés, et qu'on veux voir pour chaque élément de la 1ere liste s'il existe dans la 2eme liste (donc avec une complexité O(n*m)); Est ce qu'il serait préférable de trier la 2eme liste, puis pour chaque élément de la 1ere liste on regarde s'il existe dans la 2eme en utilisant un Binary Search par exemple ? Je ne sais pas si avec ça on aura une complexité plus importante que O(n*m) ou pas ...

Merci

[Acrim]

En supposant que tu aies un tri en n*log(n) à toi de voir. (Tu peux même trier les deux tableaux et chercher les élements qui sont dans 1 et dans 2 en (m+n) je pense).

[prgasp77]

Bonjour,
as-tu des indices sur l'ordre de grandeur du rapport n/m ?