如何加速Python中五次方数组合等式的遍历计算？

原代码采用五层嵌套循环，时间复杂度为**O(n^{5)**，当n=199时，循环次数超过3×10}10次，完全无法高效运行。以下是针对性的优化方案：

核心优化思路 #

将五层循环拆解为预存两两五次方的和，通过哈希表快速查找匹配项，把时间复杂度降至O(n²)，计算量呈数量级减少。

优化后的代码实现 #

from collections import defaultdict

# 预计算1-199的整数与其五次方值的映射
num_to_fifth = {x: x**5 for x in range(1, 200)}
# 存储所有两两五次方的和，键为和的值，值为对应的整数对列表
sum_two = defaultdict(list)

# 预填充两两五次方和的字典
for a in range(1, 200):
    a5 = num_to_fifth[a]
    for b in range(1, 200):
        b5 = num_to_fifth[b]
        sum_two[a5 + b5].append((a, b))

# 遍历所有可能的e，查找满足a⁵+b⁵+c⁵+d⁵=e⁵的组合
for e in range(1, 200):
    target = num_to_fifth[e]
    # 遍历所有两两和s1，检查是否存在s2=target-s1在sum_two中
    for s1, ab_pairs in sum_two.items():
        s2 = target - s1
        if s2 in sum_two:
            cd_pairs = sum_two[s2]
            # 输出所有符合条件的组合（打印原始整数）
            for a, b in ab_pairs:
                for c, d in cd_pairs:
                    print(f"a={a}, b={b}, c={c}, d={d}, e={e}")
                    # 若需打印五次方值，替换为：
                    # print(num_to_fifth[a], num_to_fifth[b], num_to_fifth[c], num_to_fifth[d], target)

额外优化细节 #

• 减少重复计算：如果无需区分(a,b)与(b,a)这类有序组合，可将b的遍历范围改为range(a, 200)，直接减少一半预计算量，后续可按需补充对称组合。
• 过滤无效值：遍历s1时仅保留s1 <= target的项，避免多余的查找操作，进一步提升效率。
• 内存优化：若只需要验证是否存在解而非所有组合，可改用集合存储两两和，节省内存空间。

原代码问题修正 #

原代码打印的是五次方数值而非原始整数，优化后的代码默认输出原始整数（更符合实际需求），若需打印五次方值，只需调整打印语句即可。

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