kotlin 中 Int.toString() 的时间复杂度

Question

我想知道kotlin中默认方法toString()的时间复杂度。是 O(1) 还是 O(n)。我做了一些搜索，但没有找到任何答案。例如：如果我想将 int 数组转换为 String，我使用了：

var s = ""
array.forEach{
  s+= it.toString()
}

但如果数组大小为 10^4，我将得到 TLE。如果我不使用 toString() 那么我就不会 TLE.I 知道还有其他方法可以将 Int 数组转换为 String。但我想知道 kotlin 中默认 toString() 方法的时间复杂度。 TIA

Answer 1

Kotlin 不保证 toString().

的复杂性

它可能因对象而异；每个对象都必须实现它，因此它可能取决于对象的结构及其字符串表示形式。在许多情况下，我猜它可能与字符串的长度成线性关系，但你不应该依赖它。但这确实意味着具有短字符串表示的对象可能需要足够少的时间，因此不值得担心。

特别是，对于 Ints，它很可能与字符串的大小成线性关系（因此与数字的对数成正比）。但这对任何现实世界的程序来说都不太重要。

然而， 可能重要的是 String 个对象的数量，因为它们占用内存，然后加速下一次垃圾收集。（即使对于无论“死”对象的数量如何都花费相同时间的垃圾收集器，拥有大量临时对象也会导致它们运行更频繁。在高吞吐量系统中，这可能非常重要。 )

这对于问题中的代码来说肯定是一个问题，它每次循环都会创建两个新的 String 实例！一个是调用toString()的结果；另一个是将其附加到 s 的结果。（虽然前者总是很小，但后者每次都会增长和增长，这使得 space 要求中的 二次方 。）‖ 这就是为什么 它是在循环中进行字符串连接通常是个坏主意!

当然，String 是不可变的 — 但它有一个可变的助手 class、StringBuilder。所以 几乎总是最好使用 StringBuilder 来累积结果 ，然后在最后创建一个 String（如果需要）：

val sb = StringBuilder()
array.forEach {
  sb.append(it.toString())
}
val s = sb.toString()

在这种情况下，您可以做得更好，因为 StringBuilder 重载了 append()。所以你可以直接附加一个 Int，根本不需要创建一个中间 String：

val sb = StringBuilder()
array.forEach {
  sb.append(it)
}
val s = sb.toString()

创建的唯一临时对象是 StringBuilder 的内部数组；随着内容的增长和增长，它将需要重新分配其数组来容纳它们。如果您可以估计最终结果的大小，则可以预先确定 StringBuilder 的大小以避免这种开销。

不过实际上，您可能根本不会使用循环；你会使用 joinToString()，它会为你做所有这些：

val s = array.joinToString("")

它更短、更简单、更易于阅读，和可能与手动编码的版本一样好。 Kotlin 有很多有用的扩展函数；熟悉它们非常值得！

如果您需要自己尽可能高效地构建复杂的字符串表示，而不是使用 toString() 来创建每个部分，每个相关的 class 可以有一种将 StringBuilder 作为参数并将其部分附加到 的方法。这可以让你建立一个任意复杂的字符串，根本没有任何 String 个实例！

kotlin 中 Int.toString() 的时间复杂度

Time complexity of Int.toString() in kotlin

time-complexity

kotlin