为什么回溯在 运行 时间内是线性的？
Why is traceback linear in running time?
我使用线性间隙成本实现了全局对齐。我知道填充矩阵的 运行 时间是 O(mn) 但我没有得到的是回溯的 运行 时间。
这是伪代码：
我可以看到 运行 回溯的时间是 O(n)，因为我们只迭代了一个循环。但是有人可以给我一个很好的解释吗？
假设i初始化为m，j初始化为n，终止条件为i或[=13] =] 达到零。在循环的任一迭代中，我们减少 i 或 j 或两者；在计算上，每种情况都会产生恒定成本。在至少 max{m,n} 步之后循环终止。由于可能输入大小是m*n，即矩阵的维度，
max{m,n} <= m*n
成立，这导致线性 运行 时间。
我使用线性间隙成本实现了全局对齐。我知道填充矩阵的 运行 时间是 O(mn) 但我没有得到的是回溯的 运行 时间。
这是伪代码：
我可以看到 运行 回溯的时间是 O(n)，因为我们只迭代了一个循环。但是有人可以给我一个很好的解释吗？
假设i初始化为m，j初始化为n，终止条件为i或[=13] =] 达到零。在循环的任一迭代中，我们减少 i 或 j 或两者；在计算上，每种情况都会产生恒定成本。在至少 max{m,n} 步之后循环终止。由于可能输入大小是m*n，即矩阵的维度，
max{m,n} <= m*n
成立，这导致线性 运行 时间。