python问题求解答

Question

请问大家知道这是怎么回事吗？老是运行超时，应该怎么优化一下呢？

Answer 1

这个代码的瓶颈在于它的时间复杂度是指数级别的。在每次迭代中，你都从2开始遍历到n，所以总时间复杂度为O(n^2)。

要优化这个代码可以使用一些算法来减少遍历的次数，比如质因数分解。

def prime_factorization(n):
    factors = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

# 使用示例
print(prime_factorization(n))

望采纳。