python - Python中模运算符的时间复杂度

Question

我正在尝试确定我拥有的算法的时间复杂度，但我首先需要知道 Python 中 %(模)运算符的时间复杂度。

根据 this post在 http://math.stackexchange.com ，它的时间复杂度可能类似于O(log m log n)，在某些特定情况下也可以优化为常数，但我想知道是否有人真的知道时间% 的复杂度，这样我就可以正确地确定我的算法的整体时间复杂度。

当然，我知道复杂性可能因实现而异，但我只对标准实现感兴趣。

Answer 1

这并不容易确定，因为如果我们谈论整数数学，cpython 使用不同的优化(例如，对于不超过机器字的整数，它可能是 O(1)，而对于其他可能是其他)。所以有两种方法:第一种是查看 cpython 源，第二种是测量性能(例如使用 timeit)，然后根据实验点构建外推曲线。第二种方法更好，因为你会得到一个准确的结果，而不是猜测。为了简单的目的，建立一个实验点图就足够了，如果你想要更多，你也可以使用一些回归分析方法(如最小二乘多项式拟合)。

这是 cpython 中 int 实现的源代码(查找 long_divrem 和 x_divrem 例程):https://hg.python.org/cpython/file/tip/Objects/longobject.c

添加:对于 unsigned int modulo，其使用的算法来自 Knuth 的书，即 O(MN)，其中 M+1 是商中的机器字数，N 是余数中的机器字数。对于签名，它使用自己的实现