模块化算术的时间复杂度

Question

假设我想计算一个（mod n）。这是什么时间复杂性？我正在使用Matlab，并不确定Matlab如何计算它。它是否将n除以整数部分，然后乘以n？

请问'这是什么时间复杂度'是否有意义？

Answer 1

询问有关长号码a和/或n的时间复杂性是很有意义的。相关领域被称为计算数论。例如，请参阅此book。

通常的整数算术，很可能被Matlab使用，是一个恒定时间执行的ALU操作（或多个操作）。在这种情况下，必须记住整数的大小是受限制的。

Answer 2

根据内置的帮助Matlab的计算MOD（X，Y）为：

MOD（X，Y）= X - 地板（x./y）* Y

所在楼层。函数向负无穷大旋转（即去除小数部分）。

只要您不计算mod（X，y）（其中X是一个向量），运行时将保持不变，在这种情况下，它将与向量中的元素数成线性比例关系