大多數編程語言的時間複雜度？

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這樣的基本操作的最知名的算法。