if/else for 循环的时间复杂度

Question

下面的代码会被认为是 O(1) 还是 O(n)？ for 循环具有恒定的复杂性，运行 10 次，但我不确定是否会考虑 if 条件 O(n) 或 O(1).

for (i = 0; i < 10; i++)
{
if (arr [i] == 1001)
    {
        return i;
    }
}

Answer 1

复杂度为 O(1)，因为无论您将输入增加多少，算法的复杂度都保持不变。也就是说，在该循环内执行的操作被认为具有恒定时间，因此 O(1).

for (i = 0; i < 10; i++)
{
    if (arr [i] == 1001) 
    {
        return i;
    }
}

另一方面，如果您的循环是：

for (i = 0; i < 10; i++)
{
    f(n)
}

函数 f(n) 的复杂度为 O(n) 那么整个代码片段的复杂度为 O(n) 因为 10 * N 可以标记为 O(n) .

如需更深入的解释，请查看 What is a plain English explanation of “Big O” notation?

Time complexity of for loop with if/else