Решение ^3 + b^4 = c^3 + d^3 наилучшего времени выполнения

Question

Примечание: этот вопрос отличается от " Напишите все решения для a^3 + b^3 = c^3 + d^3", потому что мне нужна помощь в понимании времени выполнения алгоритма, а не его алгоритма.

В "Взломе кодирования", 6-е издание, стр. 69, есть следующий пример:

Выведите все положительные целочисленные решения уравнения a^3 + b^3 = c^3 + d^3, где a, b, c, d - целые числа от 0 до 1000.

Вот данное оптимальное решение:

1 n = 1000
2 for c from 1 to n:
3     for d from 1 to n:
4        result = c^3 + d^3
5        append(c, d) to list at value map[result]
6 for each result, list in map:
7    for each pair1 in list:
8        for each pair2 in list:
9            print pair1, pair2

Книга утверждает, что время выполнения равно O(n^2).

Однако я не уверен, как ограничить сложность строк 6-9. Я вижу, что строки 6-7 перебирают n ^ 2 чисел, но я не вижу, как последний цикл for в строке 8 может быть постоянным временем для общего времени выполнения O(n^2).

На самом деле, я вообще не могу придумать ограничение для строки 8, потому что это зависит от длины каждого списка, который я могу сказать только меньше, чем n^2, что делает все это O(n^4),

Может ли кто-нибудь просветить меня?

Answer 1

Мое решение на с #

 var hash = new Hashtable();
        for (int i = 1; i <= n; i++)
        {
            for (int j = i + 1; j <= n; j++)
            {
                var value = Math.Pow(i, 3) + Math.Pow(j, 3);
                if (hash.Contains(value))
                    Console.WriteLine(string.Format("{0},{1},{2}", hash[value], i, j));
                else hash.Add(value, i + "," + j);
            }
        }