3

これらのパフォーマンスは何ですか？

BigInteger -> toString() // what is the runtime?

String -> toCharArray()  // what is the runtime?

ありがとう。

4

2 に答える 2

3

BigIntegerの文字列への変換はですO(N^2)。ここNで、 は結果の桁数です。内部表現の基数がターゲットの基数を割り切らない場合です。ターゲット基数がストレージ基数で割り切れる場合、変換には がかかりますO(N)。

内部表現が base-256 の場合、base 10 への変換を検討してください。10 による除算はN何回も発生する必要があります。毎回、BigInteger表現のすべての要素が変更されます。表現の要素数は出力の桁数に比例するため、全体の変換にはO(N^2).

一方、base-256 の内部表現で big int を 16 進数に変換するO(N)場合は、除算が不要なため、 がかかります。各サブエレメントは、残りのサブエレメントから分離して変換できます。サブエレメントの数は、出力の桁数に比例します。

各文字を出力にコピーする必要があるため、は文字String.toCharArray()列内の文字数です。O(N)N

于 2012-10-26T00:43:59.807 に答える
1

toString() メソッドは、たまたまネイティブ メソッドである System.arrayCopy を使用して実装されています。

public char[] toCharArray() {
    char result[] = new char[count];
    getChars(0, count, result, 0);
    return result;
}

public void getChars(int srcBegin, int srcEnd, char dst[], int dstBegin) {
    // bounds checking
    System.arraycopy(value, offset + srcBegin, dst, dstBegin,
         srcEnd - srcBegin);
}

ネイティブメソッドはおそらく O(N) であるボンネットの下で memcpy を使用しているため、ランタイム O は実際の jvm 実装に依存していると思います。このネイティブ メソッドのソースを確認するには、オープン jdk ソースを参照してください。

于 2012-10-26T03:39:17.873 に答える