メソッドはどのくらい複雑ですかmultiply、divideそして現在powはBigInteger？ドキュメント（または他のどこにも）には計算の複雑さについての言及はありません。
6464 次
4 に答える
5
BigInteger（JDKで提供される）
のコードを見ると、O（n ^ 2）multiply(..)を持っているように見えます（実際にはメソッドはです）。他のメソッドのコードはもう少し複雑ですが、ご覧ください。multiplyToLen(..)
注: これは Java 6 用です。Java 7 でも変わらないと思います。
于 2010-01-28T11:42:04.477 に答える
2
保守主義と有用な回帰テスト (巨大なデータセット) の欠如のために、sun jdk によって使用されていない新しい「より良い」 BigInteger クラスがあります。より優れたアルゴリズムを実行した人は、コメントで古い BigInteger について議論した可能性があります。
于 2010-03-16T01:37:33.167 に答える
1
それを測定します。直線的に増加するオペランドで操作を行い、図に時間を描画します。有効なベンチマーク結果を得るために、JVM をウォームアップ (数回実行) することを忘れないでください。
演算が線形 O(n)、二次 O(n^2)、多項式または指数関数である場合は明らかです。
編集: アルゴリズムに理論的な境界を与えることはできますが、実際にはあまり役に立たない場合があります。まず第一に、複雑さは要因を与えません。一部の線形アルゴリズムまたは準二次アルゴリズムは、時間とリソースを大量に消費するため、当面の問題には十分ではありません (Coppersmith-Winograd 行列の乗算など)。次に、計算には、実験によってのみ検出できるすべてのクラッジが含まれる場合があります。問題を解決するのではなく、実際のソルバー (行列条件付け) を高速化するアルゴリズムを準備しています。次善の実装があります。長すぎると、速度が劇的に低下する可能性があります (キャッシュの欠落、メモリの移動など)。したがって、実用的な目的のために、実験を行うことをお勧めします。
最良の方法は、入力の長さを毎回 2 倍にして時間を比較することです。はい、アルゴリズムの複雑さが n^1.5 か n^1.8 かがわかります。入力の長さを単純に 4 倍すると、2 ではなく 1.5 の半分の時間しか必要ありません。長さを 256 倍にすると、1.8 の時間はほぼ半分になります。
于 2010-01-28T11:42:17.550 に答える