问题描述
Java中 String #substring（）方法的时间复杂度是多少？
What is the time complexity of the String#substring() method in Java?
推荐答案
新答案
从Java 7的生命周期中的更新6开始， substring的行为更改为创建副本 - 所以每个字符串引用 char [] ，这是据我所知，不与任何其他对象共享。所以在这一点上， substring（）成为一个O（n）操作，其中n是子字符串中的数字。
As of update 6 within Java 7's lifetime, the behaviour of substring changed to create a copy - so every String refers to a char[] which is not shared with any other object, as far as I'm aware. So at that point, substring() became an O(n) operation where n is the numbers in the substring.
旧答案：pre-Java 7
未记录 - 但在实践中O（1）如果您认为不需要垃圾收集等。
Undocumented - but in practice O(1) if you assume no garbage collection is required, etc.
它只是构建一个新的 String 对象，引用相同的底层 char [] 但具有不同的偏移和计数值。因此，成本是执行验证和构建单个新（合理小）对象所花费的时间。这是O（1），因为谈论基于垃圾收集，CPU缓存等可以随时间变化的操作的复杂性是明智的。特别是，它不直接依赖于原始字符串或子字符串的长度。
It simply builds a new String object referring to the same underlying char[] but with different offset and count values. So the cost is the time taken to perform validation and construct a single new (reasonably small) object. That's O(1) as far as it's sensible to talk about the complexity of operations which can vary in time based on garbage collection, CPU caches etc. In particular, it doesn't directly depend on the length of the original string or the substring.
这篇关于Java的子串（）的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！