关于Python简单循环函数Big-O复杂度标注正确性的问询

嘿，咱们来把这两个函数的时间复杂度问题掰扯清楚！先看看你给出的代码：

def is_prime(x):
    """Take an integer greater than 1 and check if it is a prime number."""
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            return False
    return True

def multiply(a, b):
    """Take two integers and compute their product."""
    res = 0
    for i in range(1, b + 1):
        res += a
    return res

你的疑问是：标注is_prime为O(c)、multiply为*O(n)*是否正确？同时你困惑，is_prime只有单个输入，不确定它的复杂度是否随输入规模变化。咱们一步步来澄清：

先明确核心：时间复杂度看的是「输入规模」的变化，不是输入参数的数量 #

很多人会混淆这一点——输入参数的数量和输入规模完全是两回事。时间复杂度描述的是算法执行时间随输入规模增大而增长的趋势，对于数值型输入，输入规模通常指的是数值的量级（比如x是100还是10^6）。

1. 先看multiply函数 #

你的标注说它是O(n)，这个方向是对的，但要明确这里的n指的是输入b的数值规模。这个函数的循环会执行b次：比如b=100就跑100次，b=10^5就跑10^5次，循环次数和b的大小线性相关，所以它的时间复杂度是O(b)，如果用通用的n来代表输入规模的话，写成*O(n)*是没问题的。

2. 再看is_prime函数 #

你说它是O(c)（常数时间），这是不对的！它的复杂度绝对会随输入x的大小变化：
这个函数的循环是从2到int(x**0.5)+1，循环执行的次数是√x级别的。比如：

• 当x=100时，循环到10，跑8次
• 当x=10^6时，循环到1000，跑998次
• 当x=10^{12时，循环到10}6，跑近百万次

显然，x越大，循环次数越多，执行时间越长。所以它的时间复杂度是O(√x)，如果用通用的n代表x的规模，就是O(√n)，完全不是常数时间。

解开你的困惑：为什么循环不一定是O(n)？ #

你误以为循环复杂度至少是O(n)，是把“循环次数和输入的线性关系”当成了默认，但实际上循环次数的增长趋势取决于循环终止条件和输入的关系。比如is_prime的循环次数随x的平方根增长，增长速度比线性*O(n)*慢，但依然是随输入规模变化的，不是固定次数的常数时间。

总结 #

• multiply的时间复杂度是O(b)（或O(n)，n对应b的数值规模），你的这个标注是合理的，但要明确n的含义
• is_prime的时间复杂度是O(√x)，不是O(c)，它的执行时间会随输入x的增大而增长，只是增长速度比线性慢

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