Discussion :

[1tox]

Bonjour,

pour les besoins d'un comparateur d'offre pour un site web, je dois améliorer un algorithme. Voici le problème :
j'ai une liste A d'éléments numériques que nous appelerons Ai, i<N
et une liste B d'éléments numériques que nous appelerons Bj, j<N
On peut considérer que ces 2 listes sont triées par ordre croissant, i.e.
pour tout Ai, Ai<Ai+1
pour tout Bj, Bj<Bj+1
Je dois extraire une liste C constituée des 100 couples AiBj dont la somme Ai+Bj est la plus petite, i.e. telle que
Ck < Ck+1 ,k <= 100

La méthode la plus intuitive (et la moins efficace) consiste à constituer les N*N couples AiBj, à les trier et à en extraire les 100 premiers. Mais la complexité quadratique (O(n2)) de cette méthode pose un problème de performance. Est-il possible d'améliorer cet algorithme, et surtout existe-t-il un algorithme de complexité moindre qu'un algo en O(n2)?

Merci d'avance pour vos réponses futées

[Sylvain Togni]

J'ai en stock du O(100log(n)), quelqu'un a mieux ?

[1tox]

Je prends! Auriez-vous une solution gratuite à proposer ? Sinon on peut s'arranger

[pseudocode]

J'ai en stock du O(100log(n)), quelqu'un a mieux ?

En triant les 2 listes Ai et Bi et en maintenant un pointeur sur chaque liste on doit pouvoir faire mieux. Enfin je crois.

[Sylvain Togni]

En triant les 2 listes Ai et Bi et en maintenant un pointeur sur chaque liste on doit pouvoir faire mieux. Enfin je crois.

Tss, tss, tss, c'est pas si simple On ne peut pas se contenter d'avancer petit à petit l'un des deux pointeurs, il faut parfois reculer, voir repartir de zéro.


La solution que je propose est en fait en O(100log(100))

L'algorithme, qui à priori ne porte pas de nom vu que je viens de l'inventer , consiste à considérer les valeurs dans un repère, les Ai en abscisse, les Aj en ordonnées et les Ck sur la grille ainsi formée (voir figure ci-jointe).

Ensuite en raisonnant par récurrence :
- C0 = A0 + B0 (facile)
- Pour un k donné, supposons qu'on ai trouvé les C0, C1, ..., Ck (les cercles sur la figure), où chercher Ck+1 ? Réponse : sur la 4-frontière (frontière constituée des 4-voisins, i.e. les croix sur la figure), un raisonnement par l'absurde permet, par exemple, de s'en convaincre.

Cela permet donc de trouver les Ck dans l'ordre, et de s'arrêter quand on en a assez (100 par exemple).

Au niveau implémentation il suffit de maintenir deux listes ordonnées (ou arbres binaires, ...) : les Ck trouvés (cercles) et les candidats Ck+1 (croix). En effet, une liste ordonnée permet de récupérer le meilleur candidat (plus petite valeur) en O(1) et d'être mise à jour (insertion, suppression) en O(log n), n < 100 ici, d'où le O(100log(100)).

Je sais pas si j'ai été clair ?

[1tox]

L'explication est claire pour une solution qui n'est pas évidente à formuler . Il me semblait bien en effet que n ne devait pas dépasser 100 . Merci à vous et merci à Sylvain qui s'est donné la peine de faire un schéma

[pseudocode]

Tss, tss, tss, c'est pas si simple On ne peut pas se contenter d'avancer petit à petit l'un des deux pointeurs, il faut parfois reculer, voir repartir de zéro.

Of course. J'aurais du préciser qu'on ne peut pas construire la liste triée en une seule passe. Mais on doit pouvoir construire une liste de petite taille (entre 100 et N) qui contient, a coup sur, les 100 plus petites valeurs des sommes.

Reste a trier cette liste et prendre les 100 premiers.

Tout ca c'etait pour faire mieux que le log(N), mais si tu as du log(100), c'est tout bon.

[pseudocode]

Ensuite en raisonnant par récurrence :
- C0 = A0 + B0 (facile)
- Pour un k donné, supposons qu'on ai trouvé les C0, C1, ..., Ck (les cercles sur la figure), où chercher Ck+1 ? Réponse : sur la 4-frontière (frontière constituée des 4-voisins, i.e. les croix sur la figure), un raisonnement par l'absurde permet, par exemple, de s'en convaincre.

hum... ca implique que les Ai et les Bi soient triés non ?

[Zavonen]

hum... ca implique que les Ai et les Bi soient triés non ?

Cela fait partie de la donnée.

On peut considérer que ces 2 listes sont triées par ordre croissant, i.e.