2

我在很多书中读到了时间复杂度模运算。有件事我不明白。我在一些书中读到以下内容

对于任何 a mod N，a 有一个乘法逆模 N 当且仅当它与 N 互质。 N 的位）通过运行扩展的欧几里得算法。 我的问题围绕*扩展欧几里得算法* *是 O(n^3) *

当我用与netbeans或C#或C++程序集成的java编写这一行时

A = B.modInverse(N) //here by java syntax

一般来说。我可以说通常这条线的时间复杂度为 O(n^3)。

或者有必要编写相同的步骤扩展欧几里得算法。

4

1 回答 1

1

除非该modInverse方法的文档明确保证其时间复杂度，否则您通常不能对其运行时间做出任何假设。根据运行时/库甚至运行时的版本，实现可能会完全不同。

如果您有权访问源代码，则可以验证使用的是哪种算法。您还可以针对不同的输入大小运行自己的基准测试，您将获得关于具体实现的渐近行为的非常好的画面。

也就是说，用于任意精度算术的流行库很可能使用最知名的算法进行基本运算，例如modInverse.

于 2013-02-25T12:42:04.823 回答