俄罗斯农民乘法算法的时间复杂度？

Question

我想知道这段代码是俄罗斯农民实现的时间复杂度是多少

unsigned long long int russian(unsigned long long int a, unsigned long long int b) {
    unsigned long long int res = 0;
     while (b > 0) {
        if (b & 1)
            res = res + a;
        a <<= 1;
        b >>= 1;
    }
    return res % mod;
}

据我所知，我认为它的时间复杂度是 lg2b 或 lg2a（取决于我们选择的 a 或 b) 。有专家评论吗？

Answer 1

您提供的这段代码的时间复杂度当然是 O(1)，因为它可以花费多长时间有一个上限，并且永远不会超过任何输入的上限。

据推测，这不是您真正想问的问题的答案。实际上，您可能真正感兴趣的不同事物，而且它们实际上都有不同的答案。

（此外，由于您似乎在尝试进行模乘，因此您确实应该减少循环内的所有相关数量，以免溢出，并且这样您就可以使用 - 而不是 %)

您可能有兴趣精确估计挂钟时间。获得这个实际上需要收集一些经验数据，但它可能看起来像

A + B bitlength(b) + C popcount(b)

（popcount是二进制展开中1的个数）对于一些常量A、B和C。然而，CPU 硬件实际上相当复杂，并且实际上可能非常复杂才能对上面的第三项进行良好的估计，因为分支预测硬件可能会做一些奇怪的事情。

和A、B和C可能甚至都不是常量；它们将在某种程度上取决于此函数是否被内联，以及使用它的地方周围的代码类型。

现在，您可能想要一个更抽象的答案，其中 b 可以是任意大小，而不是限制为 unsigned long long 的大小，并且想要计算算术运算的次数.很明显，这只是 b 的位长度，或者如注释所示，O(lg(b))。（其中 lg 是以 2 为底的对数）

现在，您实际上可能不仅对算术运算感兴趣，而且还对它们的成本感兴趣。并且可能对 a 具有任意大小而不是限制为 unsigned long long 感兴趣。一个有用的度量单位是位操作。例如在 N 位数上左移 1 应该花费 O(N) 位操作。

我很确定循环可以执行 O(lg(a)lg(b)+lg(b)^2) 位操作。（这不包括您之后执行的 % 操作）

俄罗斯农民乘法算法的时间复杂度？

Time complexity of russian peasant multiplication algorithm?

c++

algorithm

multiplication