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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Python中模运算符的时间复杂度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1016字，纯文字阅读大概需要2分钟。

内容图文

我试图确定我所拥有的算法的时间复杂度,但我首先需要知道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是余数中的机器字的数量.
对于签名,它使用自己的实现

内容总结

以上是互联网集市为您收集整理的Python中模运算符的时间复杂度全部内容，希望文章能够帮你解决Python中模运算符的时间复杂度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端