求解a^3 + b^4 = c^3 + d^3最佳运行时

Question

注意:这个问题不同于Write all solutions for a^3 + b^3 = c^3 + d^3，因为我需要帮助理解算法的运行时，而不是算法是什么。

在破解编码采访，第6版，pg。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数循环，但我不知道第8行的最后一个for -循环如何是整个运行时的恒定时间O(n^2)。

事实上，我根本无法为第8行求出一个界，因为它取决于每个列表的长度，我只能说它小于n^2，使得整个事情O(n^4)。

有人能指点我吗？

Answer 1

我在c#中的解决方案

 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);
            }
        }