2

我试图围绕研究算法相对于比特成本（而不是单位成本）的时间复杂度的概念展开思考，似乎不可能找到任何关于该主题的内容。

这是我到目前为止所拥有的：

使用任意算术运算，两个数的 n 位乘法和除法的位成本为 O(n^2)。

因此，例如：

int number = 2;
for(int i = 0; i < n; i++ ){
    number = i*i;
}

相对于 O(log(n)^2*n) 的位成本具有时间复杂度，因为它进行 n 次乘法并且i具有log(i)位。

但在常规场景中，我们需要与输入相关的时间复杂度。那么，这种情况如何运作？中的位数i可以被认为是一个常数。这将使时间复杂度与单位成本相同，但常数更大（因此两者都是线性的）。

加法、减法、比较和分配变量都是 O(n)，n 是位数，用于任意精度算术。

4

1 回答 1

4

使用有限的精度算术（例如您的示例中最可能的 32 位int乘法），乘法的位成本是恒定的。将两个相乘的成本int是O(32^2)使用简单的乘法算法（为了更好的算法，请看这里）。这与O(1)人们在分析算法时通常忽略提及它是一样的。

但是，如果我们使用任意精度算术，那么它就变得很重要。如果一个任意长的数值i存储在位中，它将占用O(log(i))位。因此，您的代码片段的成本将是O(log(n)^2 * n)（我使用的事实是所有i的都没有大于n您的循环上升到n）。

就加法和减法而言，我会说它们都有一点成本O(n)，其中n是较小操作数的位数。

于 2012-10-06T22:09:18.600 回答