Java 子字符串的时间复杂度（）

新答案

据我所知，在Java 7的生命周期中，从更新6开始，改变的行为是创建一个副本 - 所以每个都是指一个不与任何其他对象共享的。因此，在这一点上，变成了一个O（n）运算，其中n是子字符串中的数字。substringStringchar[]substring()

旧答案：Java 7之前

未记录 - 但在实践中 O（1） 如果你假设不需要垃圾回收，等等。

它只是构建一个新对象，该对象引用相同的基础，但具有不同的偏移量和计数值。因此，成本是执行验证和构造单个新（相当小）对象所需的时间。这就是O（1），因为谈论操作的复杂性是明智的，这些操作可以根据垃圾回收，CPU缓存等在时间上变化。特别是，它不直接取决于原始字符串或子字符串的长度。Stringchar[]

在旧版本的Java中它是O（1） - 正如Jon所说，它只是创建了一个具有相同基础char[]的新字符串，以及不同的偏移量和长度。

但是，这实际上从Java 7 update 6开始发生了变化。

删除了 char[] 共享，并删除了偏移和长度字段。substring（） 现在只是将所有字符复制到一个新的字符串中。

因此，子字符串在 Java 7 update 6 中是 O（n）