python - 为什么这个脚本的运行时间是 O(n^2)？

Question

我正在阅读 McDowell 的“Cracking the Coding Interview”，我对其中一个算法有疑问(它是第 6 版第 69 页的最后一个程序)。我在下面用 Python 写了出来。它应该找到 a^2+b^2=c^2+d^2 的时间，因为 a、b、c、d 是从 1 到 1000 的整数。显然它在 O(n^2) 时间内运行。我知道双循环是 O(n^2)，但我不知道如何分析后面的三重循环。显然它是 O(n^2) 或更少，但我不知道为什么。

# This algorithm solves the above problem by making a 
# key for every unique a^2+b^2 sum... then the value for each key is
# a list of a,b tuples that I append to every time there is another a,b 
# with a given a^2+b^2 sum.
# Note that since a,b,c,d each on their own can take on any value 
# from 1 to 1000, we don't ever have to create the c^2+d^2 values
# since they will be the same as the a^2+b^2 values (the triple loop
# takes care of that idea).

sum_pair_dict = {}

n = 1001
for a in range(1,n):
    for b in range(1, n):
        sum = a**2 + b**2
        if sum in sum_pair_dict:
            sum_pair_dict[sum].append((a,b))
        else:
            sum_pair_dict[sum] = [(a,b)]

for a_sum, pair_list in sum_pair_dict.items():
    for pair1 in pair_list:
        for pair2 in pair_list:
            print(pair1, pair2)

Answer 1

• 实际算法包含在仅前 2 个 for 循环中。这会进行真正的处理(求解方程)

• 虽然确实第二个 3 个嵌套 for 循环 在 O(n^3) 中运行，但它们仅用于打印结果，实际上并没有做任何处理