带有If语句的循环的时间复杂性

Question

如果我有一个这样的循环。

for(int i=0;i<n;i++)
{
    if(i%2==0)
    {
        // do something
    }
}

如果do something代码的时间复杂度是线性的，那么时间复杂度会是多少？

Answer 1

的 if 语句每次迭代都要执行，而且是恒定时间。我们假设守护的代码是线性的。它将被执行一半的时间，但由于大O符号的工作方式，这个12的系数会掉下来。因此，总的时间复杂度是二次方的，或者说是 O(n*n).

Answer 2

当你谈论时间的复杂性时，你通常会谈论最坏的情况，所以你要考虑的条件是在 if 是真的，然后决定复杂性。

在给定的psuedo代码中。do something 有一半的时间在执行，所以 O(n/2) => O(n) 次。所以 do something 被执行O(n)次。如果 do something 是线性时间，那么代码片断是属于 O(n^2) 复杂性；