Warum ist Traceback linear in der Laufzeit?

Question

Ich implementierte globale Ausrichtung unter Verwendung linearer Lückenkosten. Ich verstehe, dass die Laufzeit zum Füllen der Matrix O (mn) ist, aber was ich nicht bekomme, ist die Laufzeit des Tracebacks. Hier ist der Pseudo-Code:

Ich kann sehen, dass die Zeit für die Rückverfolgung ausgeführt ist O (n), weil wir nur durch eine Schleife iterieren. Aber kann mir jemand eine gute Erklärung dafür geben?

Answer 1

Suppsed dass i mit m initialisiert und mit jn initialisiert wird, wird die Abbruchbedingung, daß entweder i oder j Null erreicht. In jeder Iteration der Schleife verringern wir i oder j oder beides; rechnerisch verursacht jeder der Fälle konstante Kosten. Nach mindestens Schritten endet die Schleife. Wie wahrscheinlich die Eingangsgröße m*n, nämlich die Dimensionen einer Matrix ist,

max{m,n} <= m*n 

hält, die in einer linearen Laufzeit zur Folge hat.