Question

你好，stackoverflow的好人，这是一个概念问题，可能属于math.stackexchange.com，但由于这与CPU的处理速度有关，我把它放在这里。

无论如何，我的问题很简单。我必须计算一系列数字中3个数字的立方体的和。这听起来让我很困惑，所以让我举一个例子。

我有一个数字范围，（0-100），以及每个数字立方体的列表。我必须计算出这组3个数字的每一个组合。例如，0+0+0、1+0+0、。。。98^3+99^3+100^3。这可能有道理，我不确定我是否解释得足够好。

因此，无论如何，在计算所有集合并对照数字列表检查总和是否与其中任何一个匹配之后，程序将转到下一个集合（100200）。此集合需要计算100-200+0-200+0-200之间的所有值。超过（200300）将需要做200-300+0-300+0-300，依此类推。

所以，我的问题是，根据给CPU添加的数字，所需的时间会因大小而增加吗？而且，每一组所需的时间会以可预测的速度呈指数增长吗？还是会呈指数增长，尽管不是恒定的。

Answer 1

两个数字相加的时间与数字的大小呈对数关系，或与数字的尺寸（长度）呈线性关系。

对于32位的计算机，2^32以下的数字需要1个单位的时间才能相加，2^64以下的数字则需要2个单位，等等。

Answer 2

正如我所理解的问题，第一个集合大约有100*100*100个组合（让我们忽略加法是交换的）。下一组为100*200*200，第三组为100*300*300。所以看起来你有一个O（n^2）过程在进行。因此，如果你想计算两倍的集合，它将花费四倍的时间。如果你想计算三倍的数量，它将需要九倍的时间。这不是指数（例如2^n），但通常被称为二次型。

Answer 3

这取决于“等等”持续的时间。只要你的最大数，立方，适合你最长的整数类型，就不是。它总是只需要一个指令就可以相加，所以它是恒定的时间。

现在，如果你假设一台任意精度的机器，比如用十进制符号把这些数字写在图灵机器的磁带上，那么加法需要更长的时间。在这种情况下，考虑一下需要多长时间？换句话说，想想一个十进制符号串的长度是如何增长以表示一个数字n的。这将需要至少与该长度成比例的时间。

友情链接