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

multiplier -moSTLy_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(乘数)。