IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Mathématiques Discussion :

Améliorer un algorithme de complexité quadratique


Sujet :

Mathématiques

  1. #1
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2003
    Messages
    53
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2003
    Messages : 53
    Points : 47
    Points
    47
    Par défaut 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

  2. #2
    Membre éclairé

    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 717
    Points : 858
    Points
    858
    Par défaut
    J'ai en stock du O(100log(n)), quelqu'un a mieux ?

  3. #3
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2003
    Messages
    53
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2003
    Messages : 53
    Points : 47
    Points
    47
    Par défaut
    Je prends! Auriez-vous une solution gratuite à proposer ? Sinon on peut s'arranger

  4. #4
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Sylvain Togni Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  5. #5
    Membre éclairé

    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    717
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 717
    Points : 858
    Points
    858
    Par défaut
    Citation Envoyé par pseudocode Voir le message
    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 ?
    Images attachées Images attachées  

  6. #6
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2003
    Messages
    53
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2003
    Messages : 53
    Points : 47
    Points
    47
    Par défaut
    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

  7. #7
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Sylvain Togni Voir le message
    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.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  8. #8
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Sylvain Togni Voir le message
    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 ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  9. #9
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 76
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    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.
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  10. #10
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Zavonen Voir le message
    Cela fait partie de la donnée.
    Mince, faut que j'apprenne à lire.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  11. #11
    Rédacteur
    Avatar de Zavonen
    Profil pro
    Inscrit en
    Novembre 2006
    Messages
    1 772
    Détails du profil
    Informations personnelles :
    Âge : 76
    Localisation : France

    Informations forums :
    Inscription : Novembre 2006
    Messages : 1 772
    Points : 1 913
    Points
    1 913
    Par défaut
    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 ....
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  12. #12
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par Zavonen Voir le message
    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 java : Sélectionner tout - Visualiser dans une fenêtre à part
    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 java : Sélectionner tout - Visualiser dans une fenêtre à part
    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]) );
    }
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  13. #13
    Membre du Club
    Profil pro
    Inscrit en
    Juillet 2003
    Messages
    53
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juillet 2003
    Messages : 53
    Points : 47
    Points
    47
    Par défaut
    Merci à tous pour votre participation

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Comment puis je améliorer un algorithme génétique ?
    Par speederman03 dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 26/10/2012, 19h12
  2. [D2009] Amélioration d'algorithme
    Par BuzzLeclaire dans le forum Langage
    Réponses: 14
    Dernier message: 21/06/2010, 01h03
  3. algorithmes et complexité
    Par kathia91 dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 14/01/2010, 13h48
  4. Améliorer mon algorithme A star
    Par kump_ dans le forum Algorithmes et structures de données
    Réponses: 0
    Dernier message: 16/08/2009, 16h22
  5. Améliorer l'algorithme de mon memcpy
    Par progfou dans le forum C++
    Réponses: 26
    Dernier message: 24/04/2007, 06h23

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo