for循环自增变量，时间复杂度

Question

for (int i = 1; i < a; i++){
    for(int j = 1; j < b; j = j + a){
        Function() <-- O(1)
    }
}

在这种情况下，外层循环会执行'a'次(O(a))，并且内部循环将执行 'b/a' 次(O(b/a)).

那么总的时间复杂度就是 O(a * b/a ) = O(b)?

我不是这个解释对不对..

Answer 1

嗯 O(a * b/a) = O(b) 显然是对的，因为那里有身份：O(b*a/a) = O(b*1) = O(b).

但是，时间复杂度似乎是 O(a*b*1)（假设循环不会导致时间开销）。计算量随着每个单独的循环大小线性增加。这就是 O(a*b).

的原因

Answer 2

Armen是正确的，答案是O(ab)。我们可以通过以下步骤得到答案：

O((a-1)(b-1)(1))

=O(ab-a-b+1)，其中-a-b+1可以忽略。

=O(ab)

Answer 3

我觉得这是个好问题，我的想法是

原来的复杂度应该是O(a) * O(b/a)

但在你下结论之前，你必须判断案例：

如果b <= a，则O(b/a)=O(1)，所以O(a) * O(b/a)=O(a)

如果b > a，则O(b/a)=O(b/a)，所以O(a) * O(b/a)=O(b)

结合这些情况，我会说是O(max(a,b))

Answer 4

O(b) 是不正确的，因为您通过了外循环 a 次，因此答案必须至少为 O(a)（并且据您所知，b可能比 a 小得多）。答案应该取决于 a 和 b 而不是单独的 b。

仔细算一下，你通过了内循环ceil((b-1)/a)次，因此复杂度是

O(a*ceil((b-1)/a))

但是，

ceil((b-1)/a) <= (b-1)/a + 1

因此

a*ceil((b-1)/a) <= a*((b-1)/a + 1) = b - 1 + a = a + b - 1

1渐近可忽略，因此复杂度为O(a+b)。

因为O(a+b) = O(max(a,b)) 这与@shole 的回答一致。

For loop incremented by variable, time complexity