Runtime of classi c Взломать код интервью Вопрос a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3? - PullRequest
Новая
       22

Runtime of classi c Взломать код интервью Вопрос a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3?

1 голос
/ 10 февраля 2020

Привет, я перебираю книгу CTI C Гейл Лакманн и натолкнулся на ее вопрос 

print all possible integer solutions for a^3 + b^3 = c^3 + d^3 where a,b,c,d can be integers 1 - 1000

Она дала какой-то псевдокод, который выглядит следующим образом:

Первое решение 

n = 1000
for c from 1 to n
   for d from 1 to n
      result = c^3 + d^3
      append(c,d) to list at value map[result]

for a from 1 to n
   for b from 1 to n
      result = a^3 + b^3
      list = map.get(result)
      for each pair in list
         print a, b, pair

Второе решение 

n = 1000
for c from 1 to n
   for d from 1 to n
      result = c^3 + d^3
      append (c,d) to list at value map[result]

for each result, list in map
   for each pair1 in list
      for each pair2 in list
         print pair1, pair2

Каким образом любое из этих решений получает время работы O (n ^ 2)? Даже в первом решении во втором наборе циклов for вы также перебираете пары в вашей карте, поэтому не будет ли это O (n ^ 3)?

1 Ответ

0 голосов
/ 16 февраля 2020

Если r(m) - это число упорядоченных представлений m как суммы двух положительных целочисленных кубов, то известно, что sum(r(m)^2, m=0..M) равно Theta(M^(2/3)), см. [1] .

Это означает, что число решений, которые ваш алгоритм напечатает, равно O(n^2), поскольку максимально возможная сумма из двух генерируемых вами кубов равна 2*N^3, а максимальное число решений для данного m равно r(m)^2 для учета всех комбинаций представлений по обеим сторонам уравнения.

Поскольку самый внутренний l oop всегда повторяет ровно единицы для каждого напечатанного результата, он также выполняется только самое большее O(n^2) раз, делая весь алгоритм Theta(n^2) (из-за времени итерации внешних циклов).

[1] Хули (1963): О представлениях число как сумма двух кубов ; https://link.springer.com/article/10.1007/BF01111429

...