查找数字对的时间复杂度是多少，当立方时加起来达到某个值

Question

问题如下：

给定一个整数 n，找到所有在立方时加起来为 n 的对（即 1^3 + 12^3 = 1729、9^3 + 10^3 = 1729，依此类推）

我为此找到了两种解决方案：

1）

k = ceiling(cube root of n)
for i = 1 to k
    if (cube root of (n - i^3) % 1 == 0)
        print [i, j]
    end
end

2）

i = 1
j = ceiling(cube root of n)
while (i <= j)
    if (i^3 + j^3 == n)
        print [i++, j--]
    else if (i^3 + j^3 < n)
        i++
    else if (i^3 + j^3 > n)
        j-- 
    end
end

我相信这两个都在 O（n） 上运行，其中一个比另一个有什么优势吗？

Answer 1

一般来说，计算根和类似的奇异函数是一项昂贵的操作，并且提出精确的数值结果以便您可以运行直接相等测试并不总是可能的，因此您需要额外的测试来查看您是否提出了精确的整数解决方案。所以你的第二段代码更可取。从技术上讲，它应该从 I = 0 开始。

此外，您的最佳运行时间限制是 O（n^（1/3）），而不是 O（n）。