algorithm - 时间复杂度与比特成本

Question

我正试图围绕研究算法相对于位成本(而不是单位成本)的时间复杂度的概念进行思考，似乎无法找到有关该主题的任何内容.

这是我目前所拥有的:

两个 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为位数，任意精度运算。

Answer 1

使用有限精度的算术(例如最可能的 32 位 int 乘法)，乘法的位成本是恒定的。乘以两个的成本int是O(32^2)使用朴素的乘法算法(为了更好的算法看起来 here )。这与 O(1) 相同所以人们在分析算法时通常会忽略提及它。

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

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