定义:
O(kM(n)):- modular exponentiation 的计算复杂度
其中k是指数位数，n是位数，M(n)是Newton's division algorithm的计算复杂度。
我如何确定这个计算复杂度是多项式复杂度？
事实上，符号 M(n) 是最让我困惑的。
最佳答案
想想除法算法。
除法算法的复杂度是O(n)吗？如果是，则模幂为 O(k n)。
对于某个常量 c，除法算法的复杂度是否为 O(n^c)？如果是，则模幂为 O(k n^c)。
除法算法的复杂度是O(log n)吗？如果是，则模幂为 O(k log n)。
等等
关于algorithm - 复杂度是 O(kM(n)) 多项式复杂度吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8322729/