Améliorer un algorithme de complexité quadratique

Version imprimable

17/04/2009, 14h58
1tox

Améliorer un algorithme de complexité quadratique

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 ;)
17/04/2009, 16h45
Sylvain Togni

J'ai en stock du O(100log(n)), quelqu'un a mieux ?
17/04/2009, 17h07
1tox

Je prends! Auriez-vous une solution gratuite à proposer ? Sinon on peut s'arranger ;)
17/04/2009, 17h34
pseudocode

Citation:

Envoyé par Sylvain Togni

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.
17/04/2009, 18h08
Sylvain Togni

1 pièce(s) jointe(s)

Citation:

Envoyé par pseudocode

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 ?
17/04/2009, 18h15
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 :)
17/04/2009, 19h15
pseudocode

Citation:

Envoyé par Sylvain Togni

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. :king:
17/04/2009, 19h53
pseudocode

Citation:

Envoyé par Sylvain Togni

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 ? :koi:
18/04/2009, 08h47
Zavonen

Citation:

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

Cela fait partie de la donnée.;)

Citation:

On peut considérer que ces 2 listes sont triées par ordre croissant, i.e.
18/04/2009, 12h19
pseudocode

Citation:

Envoyé par Zavonen

Cela fait partie de la donnée.;)

Mince, faut que j'apprenne à lire. :oops:
18/04/2009, 20h52
Zavonen

Je précise tout de suite que je n'ai pas fait mieux que Sylvain Togni.
Voici la voie que j'ai essayé d'explorer sans pouvoir sortir de la complexité quadratique.
Quitte à faire une (ou deux) translations on peut supposer toutes les quantités positives.
En transformant par une exponentielle on peut transformer les sommes en produits.
Le problème est alors visuellement plus simple.
On a des points Mi(ai,bi) dans le quadrant supérieur droit du plan, à chaque point on associe l'aire du rectangle ayant O comme coin inférieur gauche et Mi comme coin supérieur droit, qui est justement aibi.
Maintenant toute hyperbole y=k/x divise le nuage en deux.
Les points qui sont dans la concavité de l'hyperbole.
Les points qui sont à l'extérieur (entre les axes et l'hyperbole).
Le problème est de trouver le plus petit paramètre k tel que les points de l'extérieur sont au nombre de 100.
Je précise qu'il s'agit juste d'une façon géométrique différente de visualiser le problème.
Cependant je ne sors pas de la complexité quadratique.
Si cette visualisation inspire quelqu'un ....

Citation:

Envoyé par Zavonen

Je précise tout de suite que je n'ai pas fait mieux que Sylvain Togni.

Bah je ne pense pas qu'on puisse faire mieux que la programmation dynamique (ce que Sylvain Togni a proposé). Il faut trouver les 100 plus petites entrées dans le tableau des sommes Ai+Bj, ces 100 entrées sont forcément connexes. Donc faire mieux que 100.log(100) ca va etre dur, a moins de trouver une heuristique meilleure que l'exploration des voisins dans le tableau.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Cell implements Comparable<Cell> {		
	public int i,j,sum;
	public Cell(int i, int j, int sum) {
		this.i=i; this.j=j; this.sum=sum;
	}
	public int compareTo(Cell c) {
		return this.sum-c.sum;
	}
}
 
class CellList  {
	List<Cell> arraylist = new LinkedList<Cell>();
	public void add(Cell cell) {
		for(Cell c:arraylist)
			if (c.i==cell.i && c.j==cell.j) return;
		arraylist.add(cell);
	}
	public Cell popMin() {
		Cell cell = Collections.min(arraylist);
		arraylist.remove(cell);
		return cell;
	}		
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int[] A = new int[] { ... };
int[] B = new int[] { ... };
 
CellList tableau = new CellList();
tableau.add( new Cell(0,0,A[0]+B[0]) );
 
for(int k=0;k<100;k++) {
	// extrait la cellule avec la somme minimale
	Cell cell = tableau.popMin();
	System.out.println(cell.sum);
 
	// calcul des cellules voisines et ajout au tableau
	if (cell.i<A.length-1) 
		tableau.add( new Cell(cell.i+1,cell.j,A[cell.i+1]+B[cell.j]) );
	if (cell.j<B.length-1) 
		tableau.add( new Cell(cell.i,cell.j+1,A[cell.i]+B[cell.j+1]) );
}

20/04/2009, 09h06
1tox

Merci à tous pour votre participation :)