为什么这个脚本的运行时O（n ^ 2）？

Question

我正在经历McDowell的“Cracking the Coding Interview”，我对其中一个算法有疑问（这是第6版第69页的最后一个程序）。我使用Python在下面写了它。当a，b，c，d为1到1000的整数时，应该找到^ 2 + b ^ 2 = c ^ 2 + d ^ 2.显然它在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）中运行，但它们只是用于打印结果，而不是实际进行任何处理

Answer 2

这实际上是一个非常合理的问题，但需要一些背景来了解原因。 McDowell提供的前四种解决方案都是print解决方案的一部分。例如，之前的四个解决方案之一是：

def solve_brute_force(n):
    for a in range(1, n):
        for b in range(1, n):
            for c in range(1, n):
                for d in range(1, n):
                    if a**3 + b**3 == c**3 + d**3:
                        print(a, b, c, d)

McDowell的最终解决方案与之前的四种解决方案并不具有可比性，因为它将打印解决方案与解决方案分开。所以那不是很好。但我变得更糟：

如果print的代码结果被删除，我们只运行实际的算法（如@molamk所说）：

def solve(n):
    sum_pair_dict = {}

    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)]

    # just dump the results
    print(sum_pair_dict)

假设我们为n = 4求解，我们得到：

{
  2: [(1, 1)],
  9: [(1, 2), (2, 1)],
  28: [(1, 3), (3, 1)],
  16: [(2, 2)],
  35: [(2, 3), (3, 2)],
  54: [(3, 3)]
}

这是（IMO）和中间格式，可用于推导解决方案。例如，一个有效的解决方案是a=1，b=1，c=1，d=1。这没有在结果中表示（sum_pair_dict1）。既不是a=2，b=2，c=2，d=2，也不是a=3，b=3，c=3，d=3。

事实上，有很多结果缺失，不仅仅是那些a=b=c=d。要获得这些结果，需要后续循环：

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

好多了，现在我们看到了缺失的结果：

(1, 1) (1, 1) <------
(1, 2) (1, 2)
(1, 2) (2, 1) <------
(2, 1) (1, 2) <------
(2, 1) (2, 1) <------
(1, 3) (1, 3) <------
(1, 3) (3, 1)
(3, 1) (1, 3) <------
(3, 1) (3, 1) <------
(2, 2) (2, 2) <------
(2, 3) (2, 3) <------
(2, 3) (3, 2)
(3, 2) (2, 3) <------
(3, 2) (3, 2) <------
(3, 3) (3, 3) <------

那么，@ okcapp，我认为这值得进行修正，可以在https://careercup.wufoo.com/forms/cracking-the-book-bug-report/上提交