java - 大多数编程语言的时间复杂度？

Question

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

对于任何 a mod N，如果并且仅当它与 N 互素时。当存在此逆时，可以通过运行扩展欧几里得算法在时间 O(n^3) 中找到它(其中通常 n 表示 N 的位数)。我的问题围绕着*扩展欧几里德算法* *是 O(n^3)*

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

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

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

或者有必要写出相同步骤的扩展Euclid算法。

Answer 1

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

如果您有权访问源代码，则可以验证使用了哪种算法。您还可以针对不同的输入大小运行您自己的基准测试，您将对具体实现的渐近行为有一个很好的了解。

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