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

Question

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

根据这个帖子上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

补充：对于无符号 int 模，其使用 Knuth 书中的算法，即 O(MN)，其中 M+1 是商中的机器字数，N 是余数中的机器字数。对于签名，它使用自己的实现