这种乘法算法的时间复杂度是多少?

对于经典的访谈问题“如何在没有乘法运算符的情况下执行整数乘法?”,最简单的答案当然是C中的以下线性时间算法:

int mult(int multiplicand, int multiplier) { for (int i = 1; i < multiplier; i++) { multiplicand += multiplicand; } return multiplicand; } 

当然,有一个更快的算法。 如果我们利用向左移位的属性相当于将2乘以移位的位数的幂,我们可以向上移位到最接近的2的幂,并使用我们之前的算法加起来从那里。 所以,我们的代码现在看起来像这样:

 #include  int log2( double n ) { return log(n) / log(2); } int mult(int multiplicand, int multiplier) { int nearest_power = 2 ^ (floor(log2(multiplier))); multiplicand << nearest_power; for (int i = nearest_power; i < multiplier; i++) { multiplicand += multiplicand; } return multiplicand; } 

我无法确定此算法的时间复杂度。 我不相信O(n - 2^(floor(log2(n))))是表达这一点的正确方法,虽然(我认为?)它在技术上是正确的。 任何人都可以对此提供一些见解吗?

mulitplier - nearest_power可以和multiplier一半一样大,并且因为它倾向于无穷大,所以常数0.5并不重要(更不用说我们摆脱了大O中的常数)。 因此循环是O(multiplier) 。 我不确定比特移位。

编辑:我更多地了解了位移。 正如gbulmer所说,它可以是O(n) ,其中n是移位的位数。 但是,它在某些体系结构上也可以是O(1) 。 请参阅: 位移O(1)还是O(n)?

但是,在这种情况下无关紧要! n > log2(n)表示所有有效n 。 因此,由于上述关系,我们有O(n) + O(multiplier) ,它是O(2*multiplier)的子集,因此整个算法是O(multiplier)

找到最近功率的关键是使函数运行时可以接近运行时O(1)。 当2 ^ nearest_power非常接近您添加的结果时会发生这种情况。

在幕后,整个“2的力量”是通过位移完成的。

所以,为了回答你的问题,你的代码的第二个版本仍然是更糟糕的线性时间:O(乘数)。
你的答案O(n – 2 ^(floor(log2(n))))也不正确; 它只是非常精确,可能很难在你的头脑中快速找到界限。

编辑

让我们看看第二个发布的算法,从以下开始:

 int nearest_power = 2 ^ (floor(log2(multiplier))); 

我相信计算log2,相当令人满意的是O(log2(乘数))

那么nearest_power到达间隔[乘数/ 2到乘数],其大小是乘数/ 2。 这与找到正数的最高设置位相同。

所以for循环是O(乘数/ 2),1/2的常数出来,所以它是O(n)

平均而言,它是间隔的一半,即O(乘数/ 4)。 但这只是常数1/4 * n,所以它仍然是O(n),常数较小但仍然是O(n)。

更快的算法。

我们的直觉是我们可以在n个步骤中乘以一个n位数

在二进制中,这是使用1位移位,1位测试和二进制加法来构造整个答案。 每个操作都是O(1)。 这是长乘法,一次一个数字。

如果我们对n,x位数使用O(1)运算,则为O(log2(n))或O(x),其中x是数字中的位数

这是一个O(log2(n))算法:

 int mult(int multiplicand, int multiplier) { int product = 0; while (multiplier) { if (multiplier & 1) product += multiplicand; multiplicand <<= 1; multiplier >>= 1; } return product; } 

它本质上是我们如何进行长乘法。

当然,明智的做法是使用较小的数字作为乘数。 (我会把它作为读者的练习:-)

这仅适用于正值,但通过测试和记住输入的符号,操作正值,然后调整符号,它适用于所有数字。