4

重複の可能性:
独自の「BigInteger」クラスを作成するには、どのデータ構造を使用する必要がありますか?

純粋な興味から、私は任意の大きな整数を保持できる型を設計しようとしています。[+, -, *, /]4つの基本的な操作をサポートし、それらの操作の速度を最適化したいと思います。

ある種の二重リンクリストと、正または負の値を示すビットフラグについて考えていました。しかし、たとえば、多数の異なるサイズに追加する方法がよくわかりません。両方の数値の最後の要素に移動してから戻ります(前の要素への2番目の逆ポインターを使用)。

123456789//1つの大きな数
+       123//サイズの異なる別の大きな数

任意の大きさのメモリを使用できるとすると、このタスクに最適なデータ構造は何ですか?

算術演算の最悪の場合の複雑さについての小さなヒントとコメントをいただければ幸いです。ありがとう!

4

1 に答える 1

3

通常、この場合は配列/ベクトル、おそらくリトルエンディアン(最下位の単語が最初)を選択します。インプレース操作を実装する場合、配列を拡張するときに定数係数を使用すると、再割り当ての償却された複雑さはO(1)のままになります。

すべての操作は、O(n)ランタイムで実行可能である必要があります。ここで、nは入力のサイズです。編集:いいえ、もちろん、乗算と除算はもっと必要になります、この答えはそれが少なくともO(N log N)であることを示しています。

好奇心から:なぜホイールを再実装するのですか?ここでJavaの実装を見つけてください。C#には.NET4.0を搭載したものもあります。これを自分で実装するのは良い練習かもしれませんが(私は一度それを実行したことを覚えています)、機能が必要な場合は、すでに多くのコンピューティング環境にあります。

于 2012-07-07T22:22:16.813 に答える