Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

complexité algorithmique



  1. #1
    benoir126

    complexité algorithmique


    ------

    salut,

    J'ai une question suivante:

    soit A et B deux algorithmes pour un problème X, A ayant une complexité beaucoup moindre que B, faut-il toujours
    préférer A que B pour résoudre les instances de X ?

    Merci d'avance.

    -----

  2. Publicité
  3. #2
    GuYem

    Re : complexité algorithmique

    Si t'es pressé de voir le résultat arriver, je dirais que oui.
    Bravo jolie Ln, tu as trouvé : l'armée de l'air c'est là où on peut te tenir par la main.

  4. #3
    fderwelt

    Re : complexité algorithmique

    Bonsoir,

    Pas forcément. Il faut d'abord que la quantité de données à traiter soit suffisante pour que la différence soit perceptible. Et il faut aussi savoir si c'est une complexité moyenne (c'est en général le cas), ou une complexité max. Par exemple, quicksort est l'algorithme de tri le plus rapide en moyenne (en n.log(n)) mais il explose en n² si les données initiales sont déjà triées... Et en plus, aura-t-on affaire à des données réparties purement aléatoirement, ou y a-t-il des contraintes liées au problème particulier qui peuvent être exploitées pour rendre meilleur un algorithme par ailleurs pourri dans le cas général?
    (Je pense surtout aux algorithmes de tri, qui sont un bon exemple, mais c'est valable pour beaucoup d'autres).

    -- françois
    Les optimistes croient que ce monde est le meilleur possible. Les pessimistes savent que c'est vrai.

  5. #4
    Ksilver

    Re : complexité algorithmique

    d'accord avec fderwelt.

    d'un point de vu un peu différent, je dirait que quand on parle de compléxité en info, on parle de complexité assymptotique (avec des 0 et des grand theta), donc vrai quand n->+infinit, pour une valeur donné "pas trop grande", c'est pas dit que l'algo en O(n!) soit pas plus rapide que celui en O(lg n )

    par exemple, pour des petit tableau, le tri par insertion (en O(n²) est en general plus rapide que les tri en n*ln n (fusion, quicksort ou les trie par arbres...)

  6. #5
    benoir126

    Re : complexité algorithmique

    Ah, c'est clair.
    Merci !!!!

  7. A voir en vidéo sur Futura

Discussions similaires

  1. problème en algorithmique
    Par rasengan dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 28/10/2007, 10h01
  2. algorithmique
    Par sensor dans le forum Mathématiques du supérieur
    Réponses: 12
    Dernier message: 21/11/2006, 20h28
  3. algorithmique
    Par sensor dans le forum Mathématiques du supérieur
    Réponses: 10
    Dernier message: 05/11/2006, 17h04
  4. l'informatique pas algorithmique
    Par transhuman dans le forum Science ludique : la science en s'amusant
    Réponses: 15
    Dernier message: 25/08/2006, 20h48
  5. Algorithmique
    Par oli1978 dans le forum Logiciel - Software - Open Source
    Réponses: 4
    Dernier message: 30/06/2005, 14h35