почему время выполнения этого скрипта O (n ^ 2)?

Question

Я прохожу через «Взлом собеседования по кодированию» МакДауэлла, и у меня есть вопрос об одном из алгоритмов (это последняя программа на странице 69 6-го издания).Я написал это ниже, используя 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

Это на самом деле очень разумный вопрос, но нужен некоторый контекст, чтобы понять почему.Предыдущие четыре решения, предоставленные 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)

Окончательное решение Макдауэлла на самом деле не сопоставимо с предыдущими четырьмя решениями в том смысле, что оно отделяет печать решения от решения уравнения.Так что это не здорово.Но мне становится хуже:

Если код 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/

Answer 2

• Фактический алгоритм содержится в первых 2 только для циклов .Это делает реальную обработку (решение уравнения)

• Хотя верно, что второй 3, вложенный в циклы , работает в O (n^ 3), они только для распечатки результатов и фактически не выполняют никакой обработки