时间复杂度咨询：执行次数随输入增长但有上限的函数属于O(n)还是O(1)？

当函数的语句执行次数随输入规模增长但存在明确上限时，该函数的时间复杂度应该归类为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(1)。
• 核心原因：大O表示法描述的是输入规模n趋近于无穷大时的渐近行为。这个函数里，不管n多大，循环执行的次数最多就是1000次——n≤1000时循环跑n次，n>1000时固定跑1000次，不会随着n的无限增大而持续增加。
• 关键逻辑：大O分析看的是增长趋势，当执行次数有固定常数上限时，就属于常数时间复杂度O(1)，而非线性时间O(n)。

内容的提问来源于stack exchange，提问作者Abdulmalek Almkainzi