文章/答案/技术大牛

发布

社区首页 >问答首页 >复杂度O(kM(n))多项式复杂度吗？

问复杂度O(kM(n))多项式复杂度吗？
EN

Stack Overflow用户

提问于 2011-11-30 07:57:55

回答 2查看 732关注 0票数 1

定义：

O(kM(n))：模指数的计算复杂度

其中k是指数位数，n是数字数，M(n)是牛顿除法的计算复杂度。

如何确定这种计算复杂性多项式的复杂性？

事实上，符号M(n)是我最困惑的地方。

algorithm

complexity-theory

回答 2

Stack Overflow用户

回答已采纳

发布于 2011-11-30 08:02:51

考虑一下除法算法。

除法算法的复杂度为O(n)吗？如果是这样，则模指数是O(k )。
对于某些常数c，除法算法的复杂度为O(n^c)吗？如果是这样，则模指数是O(k ^c)。
除法算法的复杂度为O(log )吗？如果是这样，则模指数是O(k log n)。

等。

票数 1

Stack Overflow用户

发布于 2011-11-30 08:01:23

模幂运算的复杂度在指数的长度和模的长度上是多项式的，即使是规则的长除法也是如此，所以它也是多项式的一种快速除法。M(n)是将两个n位数/位数相乘(请看这里)的复杂性.

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/8322729

复制

相似问题

问复杂度O(kM(n))多项式复杂度吗？
EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问复杂度O(kM(n))多项式复杂度吗？EN

回答 2

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问复杂度O(kM(n))多项式复杂度吗？
EN