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。除以十必须发生N多次；每次，BigInteger表示的所有元素都会被修改。表示中的元素数量与打印输出中的位数成正比，因此整体转换需要O(N^2).

另一方面，在 base-256 内部表示中转换为大 int 的十六进制需要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);
}

我想本机方法可能在引擎盖下使用 memcpy，即 O(N)，因此运行时 O 取决于实际的 jvm 实现。您可能会查看开放 jdk 源以检查此本机方法的源。

于 2012-10-26T03:39:17.873 回答