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

Question

注意：这个问题不同于为a^3 + b^3 = c^3 + d^3编写所有解决方案，因为我需要帮助理解算法的运行时，而不是算法是什么。

在《破解编码访谈》(Cracking the Coding Interview， 6th Edition， 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);
}
}