这个乘法算法的时间复杂度是多少? [英] What is the time complexity of this multiplication algorithm?

问题描述

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

For the classic interview question "How do you perform integer multiplication without the multiplication operator?", the easiest answer is, of course, the following linear-time algorithm in C:

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

    return multiplicand;
}

当然，有一种更快的算法.如果我们利用左移位等于乘以2的位数乘以移位数的幂的性质，可以将其移位到最接近的2的幂，然后使用以前的算法求和从那里.因此，我们的代码现在看起来像这样:

Of course, there is a faster algorithm. If we take advantage of the property that bit shifting to the left is equivalent to multiplying by 2 to the power of the number of bits shifted, we can bit-shift up to the nearest power of 2, and use our previous algorithm to add up from there. So, our code would now look something like this:

#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))))是表达这一点的正确方法，尽管(我认为?)从技术上讲是正确的.谁能对此提供一些见识?

I'm having trouble determining what the time complexity of this algorithm is. I don't believe that O(n - 2^(floor(log2(n)))) is the correct way to express this, although (I think?) it's technically correct. Can anyone provide some insight on this?

推荐答案

mulitplier - nearest_power可以大到multiplier的一半，并且当它趋于无穷大时，常数0.5无关紧要(不是提到我们摆脱了Big O中的常量).因此，循环为O(multiplier).我不确定移位.

mulitplier - nearest_power can be as large as half of multiplier, and as it tends towards infinity the constant 0.5 there doesn't matter (not to mention we get rid of constants in Big O). The loop is therefore O(multiplier). I'm not sure about the bit-shifting.

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

I took more of a look around on the bit-shifting. As gbulmer says, it can be O(n), where n is the number of bits shifted. However, it can also be O(1) on certain architectures. See: Is bit shifting O(1) or O(n)?

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

However, it doesn't matter in this case! n > log2(n) for all valid n. So we have O(n) + O(multiplier) which is a subset of O(2*multiplier) due to the aforementioned relationship, and thus the whole algorithm is O(multiplier).

这篇关于这个乘法算法的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！