为什么一个求因数的Python函数比另一个快3000%以上？

核心原因1：循环遍历范围的量级差异 #

因数存在基础数学性质：若正整数i是x的因数，则x//i也必然是x的因数，所有因数都成对出现在√x的两侧，无需遍历到x本身就能找到全部因数。

• 慢代码的循环范围是range(1, int(x))，当x为50000000时，需要执行近5000万次模运算判断，时间复杂度为O(n)
• 快代码利用上述数学性质，仅遍历到√x即可，循环范围为range(1, int(x**0.5))，x=50000000时√x约为7071，仅需要执行7000多次循环，时间复杂度降到O(√n)，仅为慢代码循环次数的1/7000，这是效率差距的最核心来源。

核心原因2：重复排序的执行次数差异 #

两段代码都存在一处可优化的冗余操作：在循环内部每次找到因数后就执行sort()排序，单次排序的时间复杂度为O(k log k)（k为当前列表长度），累计开销会被循环次数放大：

• 慢代码循环次数极多，且每找到一个因数就排序一次，累计的排序开销远高于快代码
• 实际编码中可以去掉循环内的排序操作，在循环结束后统一执行一次排序，能进一步提升运行速度。

可落地的优化版写法 #

原快代码还存在两处小问题：会漏掉刚好等于√x的因数、平方数场景下会重复添加相同因数，优化后写法如下：

def divisor_opt(x):
    divisors = []
    # 遍历范围加1，避免漏掉刚好为平方根的因数
    for i in range(1, int(x**0.5) + 1):
        if x % i == 0:
            divisors.append(i)
            # 避免平方数场景下重复添加相同因数
            if i != x // i:
                divisors.append(x//i)
    # 最后统一排序一次，减少排序开销
    divisors.sort()
    return divisors

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