在Java中,对于字符串x,s.length()的运行时成本是多少？是O(1)还是O(n)？

Question

我被告知代码如:

for (int i = 0; i < x.length(); i++) {
    // blah
}

实际上是O(n ^ 2),因为重复调用x.length().相反,我应该使用:

int l = x.length();
for (int i = 0; i < l; i++) {
    // blah
}

这是真的？字符串长度是否存储为String类的私有整数属性？或者String.length()真的走完整个字符串只是为了确定它的长度？

Answer 1

不,java字符串的长度是O(1),因为java的字符串类将长度存储为字段.

你收到的建议对C来说是正确的,在其他语言中,但不是java.C的strlen遍历char数组,寻找字符串结尾的字符.Joel在播客上讨论过它,但是在C的背景下.

Answer 2

与到目前为止所说的相反,不能保证String.length()字符串中包含的字符数是恒定时间操作.String类的javadoc 和Java语言规范都不需要String.length是一个恒定的时间操作.

但是,Sun的实现String.length()是一个恒定的时间操作.最终,很难想象为什么任何实现都会为此方法实现非恒定时间实现.

Answer 3

String将长度存储在单独的变量中.由于字符串是不可变的,因此长度永远不会改变.它只需要在创建时计算一次长度,这是在为其分配内存时发生的.因此它的O(1)

Answer 4

如果您不知道可以这样写：

for (int i = 0, l = x.length(); i < l; i++) {
    // Blah
}

由于l的范围较小，因此它稍微干净一些。