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是较小者的位数操作数。