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

Question

我在很多书中阅读了时间复杂度模块化算法。有不明白的东西。 我在一些书阅读以下

对于任何一个模N，一个具有乘法逆模N如果 且仅当它是相对素N.当这种逆存在，它可以在时间O实测值（n^3）（通常n表示N的位数），通过运行扩展Euclid算法。 我的问题是围绕* 扩展欧几里得算法 * * 是具有为O（n^3） *

当我在Java用netbeans或C＃或C++程序这一行集成写

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

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

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

Answer 1

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

如果您有权访问源代码，则可以验证使用哪种算法。您也可以针对不同的输入大小运行您自己的基准测试，并且您会对具体实现的渐近行为有一个很好的描述。也就是说，用于任意精度算术的流行库极有可能使用像modInverse这样的基本操作的最知名的算法。