Java的String类中length()函数的复杂性是什么？

Question

是O(n)还是O(1)(通过在对象的字符串分配期间保存私有变量的长度).

如果它是O(n),它是否意味着下面代码的复杂性是O(n ^ 2)？

for(int i=0; i<s.length()-1;i++){
    //some code here!
}

Answer 1

它O(1)的长度已经为String实例所知.

从JDK 1.6可以看出它.

public int length() {
    return count;
}

更新

重要的是要理解为什么他们可以缓存值count并继续使用相同的值count.原因在于他们在设计时做出了很大的决定String,其不变性.

Answer 2

在 Java 中，任何字符串都由数组支持final。所以很简单，只返回数组长度。所以这就是O(1)复杂性。如果你在代码中思考

for(int i=0; i<s.length()-1;i++){
    //some code here!
}

s.length()每次迭代都会被调用，那么你是不对的。现代编译器优化了这种类型的调用并更改s.length()为常量（即String实例的长度）。