我正在尝试查找包含 a%p 计算的算法的运行时间。如果 a 和 p 是 n 位数，这一步需要多长时间？
问问题
7466 次
2 回答
5
O(1)如果您使用硬件实现，则模运算是 on 。（原因是，对同一组有限输入值的每个操作都在 中O(1)）否则，任意长度整数的任何软件实现都应该具有与相同输入数字除法相似的复杂性。我不确定那到底是什么。
编辑：我有预感，O(n²)但我没有准备好证明。
EDIT2：很难对此提供完整和正确的答案，因为复杂性不取决于问题，而是取决于实现，因此，不同的实现具有不同的复杂性，问题只能给出可实现性能的下限的求解算法。
然而，目前还没有乘法复杂度的下限。并且由于模的下限实际上取决于乘法的下限（请参阅评论中发布的链接。我读过它，这是好东西！），模实现的复杂性也没有下限，并且所以我们无法准确估计模数的可实现性能。
但是由于我们谈论的是 Big-O 表示法，我可以肯定地说，任何体面的模实现在 in 中O(n²)，并且大多数都在O(n²).
于 2013-02-01T19:30:54.683 回答
0
它是 O1，因为 int 或 long 的位是恒定的
于 2017-09-08T20:35:25.077 回答