c - 这个乘法算法的时间复杂度是多少？

Question

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

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

    return multiplicand;
}

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

#include <math.h>

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))))是表达这一点的正确方法，尽管(我认为？)它在技术上是正确的。任何人都可以对此提供一些见解吗？

Answer 1

mulitplier - nearest_power可以大到 multiplier 的一半，并且随着它趋于无穷大，常数 0.5没关系(更不用说我们摆脱了 Big O 中的常量)。因此循环是 O(multiplier) .我不确定位移位。

编辑:我更多地了解了位移位。正如 gbulmer 所说，它可以是 O(n) ，其中 n是移位的位数。但是，它也可以是 O(1)在某些架构上。见:Is bit shifting O(1) or O(n)?

但是，在这种情况下没关系! n > log2(n)对于所有有效 n .所以我们有 O(n) + O(multiplier)这是 O(2*multiplier) 的子集由于上述关系，因此整个算法是O(multiplier) .