Java中的toCharArray()和toString()的运行时间是什么？

Question

这些的性能如何？

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

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

谢谢。

- knd

---

这个问题有什么好处？ - Lews Therin

这个问题不太有意义。你在寻找什么样的答案？ - Ted Hopp

假设字符串中有n个字符，将其转换为大小为n的数组的大O是多少？ - knd

Answer 1

BigInteger 转换为字符串的时间复杂度为 O(N^2)，其中 N 是结果中数字的位数，当内部表示的基数不能被目标基数整除时；当目标基数可被存储基数整除时，转换需要 O(N) 的时间复杂度。

考虑将内部表示为基数 256 的大整数转换为十进制。需要进行 N 次除以 10 的运算；每次操作都会修改 BigInteger 表示中的所有元素。表示中的元素数量与输出中的位数成比例，因此总的转换时间复杂度为 O(N^2)。

另一方面，在将基数为 256 的大整数转换为十六进制时，时间复杂度为 O(N)，因为此时不需要进行除法运算。每个子元素可以独立于其余元素进行转换，而子元素的数量与输出中的位数成比例。

至于 String.toCharArray()，它的时间复杂度为 O(N)，其中 N 是字符串中字符的数量，因为每个字符都必须被复制到输出中。

- Sergey Kalinichenko

---

你确定 toCharArray 是 O（N） 而不是 O（1） 吗？毕竟字符串已经以字符数组的形式存储了。 - arshajii

Java中的数组是可变的，而字符串则是不可变的。toCharArray方法必须复制长度为N的副本，导致时间复杂度为O(N)。 - Sergey Kalinichenko

哦，现在通过查看源代码，我发现他们确实将所有字符复制到一个新数组中。 - arshajii

你确定 BigInteger.toString 对于某些基数是“O（N）”，而对于其他基数是“O（N ^ 2）”吗？查看源代码，不同基数值的执行路径或循环计数之间差别不大。看起来它会一次一个 int 进行合成除法，并将乘积和余数向前传递。这使它在任何情况下都是 O（N）。 - Ted Hopp

@TedHopp 我们可能在看不同的源代码：我在这里看到的链接上，第1471行有format方法。它有一个特殊情况是针对基数16的，时间复杂度为O(N)，而其他情况（从第1502行开始）则看起来是O(N^2)。 - Sergey Kalinichenko

Answer 2

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实现。您可以查看open jdk源代码以检查此本地方法的源代码。

- Matt