Canal-U

4.10. Cet algorithme est-il efficace ?

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