algorithm - 嵌套 for 循环时间复杂度与函数调用

Question

 for(i = 1; i < a; i++){
    for(j = 1; j < b; j = j + 3){
      if((i+j) % 2 == 0)
          Func()
 }
} 

在这种情况下，我认为是 O(a*b) 和 Theta(a*b)。

我是否正确分析了复杂性？

Answer 1

首先，你，大概是说

 if ((i + j) % 2 == 0)

代替

 if (i + j % 2 == 0)

因为当 i 为正时，j % 2 非负 那么 i + j % 2 是正数，因此 i + j % 2 从不 等于零:Func() 根本不运行。

你的答案是正确的:复杂度是

 a *      // from the first loop
 b / 3 *  // from the second loop
 1        // from the condition (it always true)

所以你有

 Θ(a * b / 3 * 1) = Θ(ab)