algorithm - 带 If 语句的循环的时间复杂度

Question

如果我有这样的循环:

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

如果//do some 代码的时间复杂度是线性的，那么时间复杂度是多少。

Answer 1

当您谈论时间复杂度时，您通常会谈论最坏的情况，因此您考虑 if 中的条件为 true，然后决定复杂度。

在给定的伪代码中，do some 执行了一半的时间，因此 O(n/2) => O(n) 次。所以do some执行了O(n)次。如果做某事是线性时间，那么代码片段的复杂度是O(n^2)。