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

标签 algorithm time-complexity complexity-theory

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

在 Cracking the Coding Interview,第 6 版,pg。 69,有下面的例子:

Print all positive integer solutions to the equation a^3 + b^3 = c^3 + d^3, where a, b, c, d are ints between 0 and 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) .

有人可以启发我吗?

最佳答案

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

关于algorithm - 求解 a^3 + b^4 = c^3 + d^3 最佳运行时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44859599/

相关文章:

javascript - 将两个多维数组映射到一个对象中

Python any 和 in 和 for 循环的时间复杂度

python - 自守程序的长时间运行

java - 字符串匹配和整数匹配的时间复杂度

algorithm - 嵌套算法的计算复杂度

algorithm - 增量计算背包

python - 有人能告诉我 python 中随机函数的内部工作原理吗?

java - 按索引从周期序列 0,1,2,3,2,1,0,1... 获取值的最简单方法是什么?

c - 检测文件 A-Z 和 AA-ZZ 中的字母

c++ - 对于像 C++ 这样的现实世界语言,时间复杂度有一致的定义吗?