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

EN

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

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

添加:对于无符号整数模数，它使用的算法来自Knuth的书，它是O(MN)，其中M+1是商中的机器字的数量，N是余数中的机器字的数量。对于签名，它使用自己的实现

对于大整数，Python除法(和模数)使用O(n^2)算法。乘法使用0(n^1.585)的Karatsuba乘法，但除法使用基本的“小学”除法。