complexité algorithmique

[invite997f7e79]

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.

-----

[invitedf667161]

Si t'es pressé de voir le résultat arriver, je dirais que oui.

[invite6de5f0ac]

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

[invite4ef352d8]

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...)

[A voir en vidéo sur Futura]

[invite997f7e79]

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