Complexité d'algorithmes
Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

Complexité d'algorithmes



  1. #1
    pierrerocher

    Complexité d'algorithmes


    ------

    Bonjour,
    Lorsqu'on a le choix entre deux algorithmes, faut-il systématiquement choisir l'algorithme dont l'ordre de grandeur de la complexité en moyenne est le plus petit ?

    J'aurais envie de dire oui mais si ça se trouve il peut exister des cas où ce n'est pas conseillé : en connaissez-vous ?

    -----

  2. #2
    pm42

    Re : Complexité d'algorithmes

    Il y a plein de cas où on n'utilise pas les algorithmes avec la complexité moindre parce que leur implémentation est trop lourde ou parce qu'en pratique, ils ne deviennent plus efficaces que pour des tailles plus grandes que celles qu'on manipule.

    Tu peux regarder https://en.wikipedia.org/wiki/Comput...cal_operations par exemple et tu verras qu'il y a des algorithmes pour la multiplication qui sont d'une complexité très faible.
    Et on ne s'en sert pas.

    Tu peux aussi regarder les produits de matrice sur le même lien.

  3. #3
    pierrerocher

    Re : Complexité d'algorithmes

    Merci beaucoup pour ta réponse rapide !
    Je vais regarder ça.

  4. #4
    Chanur

    Re : Complexité d'algorithmes

    Oui, tout simplement le cas où le volume de données est petit. Il sera souvent préférable d'utiliser un algorithme simple et lent qu'une usine à gaz inutile.

    Par exemple, suppose que tu cherche un élément dans une liste.
    L'algo le plus simple est de comparer ton élément à chaque élément de la liste.
    Si c'est une liste de 10 éléments , c'est suffisant (sauf si tu as à faire la recherche des milliards de fois)
    Si ta liste comporte des millions d'éléments, il sera sans doute plus intéressant de la trier et de faire une recherche dichotomique.
    Si ta liste compte 100 milliards d'élément, même le tri va être dur : il faut sûrement réfléchir à d'autres solutions, en essayant de profiter des particularités de la liste, et en tenant compte du nombre de fois où tu vas faire la recherche.

    Un autre exemple courant est l'inversion de matrices : on ne raisonne pas du tout de la même façon si c'est une matrice 3x3 ou si c'est une matrice 1000000x1000000.

    [edit] Grillé par PM42 ! [/EDIT]
    Ce qui se conçoit bien s'énonce clairement ; et les mots pour le dire arrivent aisément.

  5. A voir en vidéo sur Futura
  6. #5
    Evil.Saien

    Re : Complexité d'algorithmes

    Hello,

    Tout à fait d'accord avec pm42 et Chanur.

    Un autre exemple bien connu (souvent donné en exercice d'ailleurs) concerne la convolution (avec des images 2D par exemple). On peut calculer un seuil T tels que, étant donnée une image de taille NxN, le calcul de la convolution dans l'espace image est plus rapide pour N < T alors que pour N > T il est plus rapide de faire la convolution dans l'espace de fourier via FFT.
    Mon psychiatre, pour quinze mille francs, il m'a débarrassé de ce que j'avais : quinze mille francs

Discussions similaires

  1. Algorithmes
    Par invited3379a2d dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 30/08/2010, 19h20
  2. Complexité des algorithmes
    Par egondragon dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 31/07/2010, 13h31
  3. les algorithmes de Tri
    Par inviteddeac092 dans le forum Logiciel - Software - Open Source
    Réponses: 14
    Dernier message: 21/11/2009, 17h07
  4. complexité des algorithmes
    Par invite26699713 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 18/09/2009, 18h15
  5. Complexité algorithmes
    Par invite12d3041b dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 26/03/2009, 22h10