Java 中 String.length（）的时间复杂度是多少？

time-complexity java

2022-09-04 05:48:11

是 O（n）还是 O（1）（通过在字符串分配给对象期间将长度保存在私有变量中）？

如果是O（n），是否意味着以下代码的复杂度是O（n^2）？

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

答案 1

这是因为长度已经知道实例。O(1)String

从JDK 1.6中可以看到它。

public int length() {
    return count;
}

更新

了解为什么它们可以缓存的值并继续使用相同的值非常重要。原因在于他们在设计时做出的一个伟大的决定，它的不变性。countcountString

答案 2

在Java中，任何字符串都由数组备份。因此，只需返回数组长度就很简单。这就是复杂性。如果你在代码中思考finalO(1)

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

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

Java 中 String.length（） 的时间复杂度是多少？