嵌套循环的时间复杂度，其中第二个循环仅针对上述循环的最后一次迭代进行迭代
Time complexity of nested loop where the second loop iterates only for the last iteration of the above loop
想象一个场景，其中第二个循环对于 n 的每次迭代都迭代一次，除了最后一个循环迭代 m 次：
// n and m are two different variables.
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(i!=(n-1)) break;
// O(1) code here.
}
}
这个的时间复杂度是多少？是 O(n*m)、O(n+m) 还是其他？
编辑：由于误读，原来的答案是错误的。
这是 O(n + m)，因为对于最外层循环的 n - 1 次迭代，完成了恒定量的工作：它启动内层循环并在第一次迭代时中止。对于最外层循环的最后一次迭代，最内层循环迭代 m 次，每次迭代执行恒定量的工作。所以，我们有 (n - 1) * x + 1 * (m * y) 步，其中 x 和 y 是一些常数。我们知道 (n - 1) * x + 1 * (m * y) = O(n + m) 因为我们可以去掉自变量 n 和 m 上的常数因子。
想象一个场景，其中第二个循环对于 n 的每次迭代都迭代一次，除了最后一个循环迭代 m 次：
// n and m are two different variables.
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(i!=(n-1)) break;
// O(1) code here.
}
}
这个的时间复杂度是多少？是 O(n*m)、O(n+m) 还是其他？
编辑：由于误读，原来的答案是错误的。
这是 O(n + m)，因为对于最外层循环的 n - 1 次迭代，完成了恒定量的工作：它启动内层循环并在第一次迭代时中止。对于最外层循环的最后一次迭代，最内层循环迭代 m 次，每次迭代执行恒定量的工作。所以，我们有 (n - 1) * x + 1 * (m * y) 步，其中 x 和 y 是一些常数。我们知道 (n - 1) * x + 1 * (m * y) = O(n + m) 因为我们可以去掉自变量 n 和 m 上的常数因子。