Partie Théorie : Questions/Discussions

Salut Lucas,

On peut écrire un alogrithme en O(n1 +n2) si les deux listes sont ordonnées. L’idée est que tu as deux pointeur, un pour chaque liste (des variables [a et b] qui contiennent des indexes). À chaque fois on calcule l’écart entre les deux éléments de la liste et on regarde s’il est plus petit que le plus petit qu’on a trouvé jusqu’à ce point. Pour la prochaine itération on essaie de minimiser la distance entre les deux en incrément l’index du élément plus petit.

Tu trouve le algorithme comme image attaché à ce message.

Beau week-end 

Parzival

Ps.
Souvent on peut identifier le type l’algorithme qu’on aura besoins en regardant la complexité demandé. Ça viendra avec l’entraînement. Par exemple si O(log n) est demandé il est très probable que la réponse demande un algorithme utilisant le principe d’une recherche dichotomique. etc. Avec O(n1+n2) normalement c’est un indice qu’on doit faire une itération sur deux listes avec une seule boucle. Cette complexité donne nous aussi la restriction qu’on ne devra pas utiliser des algorithmes des tris.