Vidéo pédagogique
Notice
Lieu de réalisation
Grenoble
Sous-titrage
Sous-titre
Langue :
Anglais
Crédits
François Rechenmann (Intervention)
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées 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.
DOI : 10.60527/eger-0y67
Citer cette ressource :
François Rechenmann. Inria. (2015, 5 février). 4.10. How efficient is this algorithm? , in 4. Sequences comparison. [Vidéo]. Canal-U. https://doi.org/10.60527/eger-0y67. (Consultée le 21 juillet 2024)

4.10. How efficient is this algorithm?

Réalisation : 5 février 2015 - Mise en ligne : 9 mai 2017
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

We have seen the principle of an iterative algorithm in two paths for aligning and comparing two sequences of characters, here DNA sequences. And we understoodwhy the iterative version is much more efficient than the recursive version. But, how efficient is reallythis iterative algorithm? You remember that in order to measure the efficiency of algorithms, the computer scientists do not use any mean of measuring the time or any other thing. They evaluate the number of timethe main operation inside the algorithm is executed. In the caseof this Needleman and Wunsch algorithm which has been published 40 years ago, the operation which is critical is the comparisonbetween two letters of a pair of letters. It's easy, if you look at the algorithm, to find that the number of comparison is of the order of N multiplied by M with N and M being the lengths of the sequences. We say that the algorithmic complexity of this algorithm is quadratic. What does it mean? It means thatif the lengths of the sequences double, the execution time will be multiplied by four. It's easy to see. First, you have two sequences of lengths N and M. You double the length of the first sequence and you double the length of the fourth sequence since the number of comparison is the result of the multiplication of these two values, you see that of course you multiply the execution time by four.

Intervention

Dans la même collection

Avec les mêmes intervenants et intervenantes