2

私は多くの本で時間複雑度モジュラー算術について読みました。わからないことがあります。私はいくつかの本で次のことを読みました

任意の a mod N について、a は、N に対して互いに素である場合に限り、N を法とする乗法逆行列を持ちます。この逆行列が存在する場合、時間 O(n^3) で見つけることができます (通常、n は数を示します)。拡張 Euclid アルゴリズムを実行することにより、N のビット)。 私の質問は*拡張 Euclid アルゴリズム* *は O(n^3) を持っています*

NetbeansまたはC＃またはC ++プログラムと統合されたJavaでこの行を書くとき

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

一般に。通常、この行の時間の複雑さは O(n^3) と言えますか。

または必要に応じて同じ手順を記述して、Euclid アルゴリズムを拡張します。

4

1 に答える 1

1

メソッドのドキュメントでmodInverse時間の計算量が明示的に保証されていない限り、通常、実行時間について推測することはできません。実装は、ランタイム/ライブラリまたはランタイムのバージョンによって完全に異なる場合があります。

ソース コードにアクセスできる場合は、どのアルゴリズムが使用されているかを確認できます。さまざまな入力サイズに対して独自のベンチマークを実行することもでき、具体的な実装の漸近的な動作についてかなりよく理解できます。

とは言うものの、任意精度の算術演算用の一般的なライブラリは、modInverse.

于 2013-02-25T12:42:04.823 に答える