时间复杂度随着输入而增加但有限制的算法是否被视为 O(n)？

Question

如果函数的语句执行随着输入的增加而增加但有限制，那么它会被视为 O(n) 还是 O(1)？

例如：

void func(int n)
    {
        if (n > 1000)
        {
            for (int i = 0; i < 1000; i++)
            {
                //do thing
            }
        }
        else
        {
            for (int i = 0; i < n; i++)
            {
                //do same thing
            }
        }
    }

这个函数是 O(n) 还是 O(1)？

Answer 1

它是 O(1)，而不是 O(n)。

Big-O 分析是渐近的：它故意忽略性能函数的任意大的初始部分，以便准确描述大规模行为。