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

Question

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

在 Cracking the Coding Interview，第 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);
            }
        }