Pourquoi traceback est-il linéaire dans le temps de fonctionnement?

Question

J'ai implémenté l'alignement global en utilisant le coût d'écart linéaire. Je comprends que le temps de remplissage de la matrice est O (mn) mais ce que je ne comprends pas, c'est le temps de traçage. Voici le pseudo-code:

Je vois que le temps en cours d'exécution pour retraçage est O (n) parce que nous Itère une seule boucle. Mais quelqu'un peut-il me donner une bonne explication pour cela?

Answer 1

Suppsed que i est initialisé avec m et j est initialisé avec n, la condition de terminaison est que soit i ou j atteint zéro. Dans l'une ou l'autre itération de la boucle, nous diminuons i ou j ou les deux; calcul, chacun des cas encourt un coût constant. Après au moins max{m,n} étapes la boucle se termine. Comme probablement la taille d'entrée est m*n, à savoir les dimensions d'une matrice,

max{m,n} <= m*n 

détient, ce qui donne un temps de fonctionnement linéaire.