Vidéo pédagogique

4.10. Cet algorithme est-il efficace ?

Réalisation : 1 juin 2015 Mise en ligne : 1 juin 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3
Descriptif

La version itérative de notre algorithme d'alignement optimal de séquences est indéniablement beaucoup plus efficace que sa version récursive, puisque nous avons vu qu'il permettait d'éviter que le coût d'un même nœud soit réévalué plusieurs fois.Mais qu'en est-il véritablement de l'efficacité de cet algorithme ? Eh bien encore une fois, pour mesurer les performances en temps d'un algorithme, les informaticiens ne font pas de chronométrage, ils calculent le nombre d'opérations qui doivent être effectuées pour que l'algorithme aboutisse à son résultat. Ici dans le cadre de cet algorithme de Needleman et Wunsch qu'ils ont proposé en 1970, on voit vite que le nombre d'opérations à exécuter - comparaisons et calculs qui vont autour - est de l'ordre de N fois M où N est la longueur de la première séquence et M la longueur de la seconde. On dira que la complexité algorithmique est quadratique, on oublie la différence entre N et M et on dit tout simplement que quoi ? La complexité est quadratique de l'ordre de N au carré où N est la longueur des séquences, peu importe qu'elle soit la même ou différente...

Intervenants
Thèmes
Notice
Sous-titrage
Sous-titre
Langue :
Français
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusés sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
Citer cette ressource:
Inria. (2015, 1 juin). 4.10. Cet algorithme est-il efficace ?. [Vidéo]. Canal-U. https://www.canal-u.tv/87359. (Consultée le 17 mai 2022)
Contacter
Documentation

Dans la même collection

Avec les mêmes intervenants

Sur le même thème