我试图确定我所拥有的算法的时间复杂度,但我首先需要知道Python中％(modulo)运算符的时间复杂度.

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

当然我知道复杂性可能会从实现变为实现,但我只对标准实现感兴趣.

解决方法:

这并不容易确定,因为如果我们谈论整数数学,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是余数中的机器字的数量.
对于签名,它使用自己的实现