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

Si je comprends bien, les questions sont :
 
Q1 : Serait-il avantageux d'avoir des listes triées ?
R1 : Oui, car cela permet de faire une recherche dichotomique (nom français du "binary search" ).
Une autre solution, serait de faire une table de hachage, qui pourrait donner des résultats encore meilleurs.
 
Q2 : Faudrait-il regarder d'abord la deuxième liste avant la première, ou l'inverse ?
R2 : L'ordre ne me semble pas important.

- Cas A : listes non triées :
  pour chaque élément de L1 (O(n)), on cherche s'il existe dans L2 (O(m)):
  O(n*m)
- Cas B :  
  On trie L2 (O(m log(m)))
  pour chaque élément de L1 (O(n)), on cherche s'il existe dans L2 (O(log(m))
  O((m + n) log(m)) => mieux que O(n * m)

À rajouter le fait que la réponse dépend aussi de l’implémentation.
Certaines implémentation pouvant être parallélisé alors que d'autres non