内循环仅运行一次时嵌套循环的时间复杂度？

Question

我有以下代码，正在尝试计算它的时间复杂度：

int sum(int m, int n, int K) {
    int s = 0;
    for (int i = 0; i < n; i++) {
        s += i;
        if (i == K % 2) {
            for (int j = 0; j < m; j++) {
                s += j;
            }
        }
    }
    return s;
}

根据代码，外循环运行复杂度为O(n)，内循环运行复杂度为O(m)。但是，内部循环只执行一次（当i 等于K % 2 时）。我不确定只有运行一次时的时间复杂度是 O(nm) 还是 O(n + m)。目前，我怀疑复杂度应该是 O(n + m)。有人可以为我解释一下这个案例吗？

Answer 1

是O(m + n)，因为内循环只运行一次。

你通常将内循环的 O(m) 复杂度乘以 n 的原因是因为通常，内循环被执行 n 次。我们应该将每个操作的复杂性乘以它完成的次数。在这种情况下，O(m)操作被执行一次，所以你应该乘以1，而不是n。

更具体地说，赋值s += i;和比较i == K % 2总共进行了n次，而赋值s += j;是总共完成 m 次，因此总步数为 O(m + n)。没有执行 mn 次或 mn 次的任何倍数的操作。

内循环仅运行一次时嵌套循环的时间复杂度？

Time complexity of nested loop when inner loop only run once?

time-complexity

nested-loops