algorithm - 了解 Big Oh Careercup 破解编码面试

Question

Careercup Cracking Coding Interview(CCIS)一书中有一道例题。

打印方程的所有正整数解a³ + b³=c³ + d³和 d 是 1 到 1000 之间的整数。

他们给出了三种解决方案，我将在此处展示其中两种。

示例 1


1 n = 1000
2 对于从 1 到 n
3 对于 b 从 1 到 n
4 代表 c 从 1 到 n
S 代表 d 从 1 到 n
6 如果 a^3 + b^3 == c^3 + d^3
7 打印 a、b、c、d


示例 2

1 n = 1000
2 对于从 1 到 n
3 对于 b 从 1 到 n
4 代表 c 从 1 到 n
5 d = pow(a3 + b3 - c3 , 1/3)//将舍入为 int
6 if a^3 + b^3 == c^3 + d^3//验证该值有效
7 打印 a、b、c、d


书上说第一个问题是O(n⁴)，第二个是O(n³)。我的问题是为什么他们忽略了 pow

的复杂性

Answer 1

你可以说他们不是忽略它，而是假设复杂度是O(1)。理由如下:

您需要创建一个函数来计算从 0 到 1000^3 的某个数字的立方根(整数值)。你将如何实现它？一种简单的方法是二进制搜索(存在更好的方法，如数值方法)。您需要多少次迭代:log2(1000^3) 大约是 30。这样的 O(1)。