Java StringBuilder.setLength() - 时间复杂度是否为O(1)?

Question

我计划对StringBuilder中的许多字符进行删除操作。使用sb.setLength(sb.length() - 1);的解决方案对我来说很好。但是，由于这些删除操作将在循环中执行，因此我需要知道它的复杂度。

我的理解是，该操作仅递减StringBuilder对象的某个私有属性，并且不执行任何字符本身的复制/克隆/复制等操作，因此时间复杂度为O(1)，应该能够快速完成。

我理解正确吗？

- alekscooper

---

如果你使用Java编程，那么你应该使用一个集成开发环境(IDE)，并且它应该能让你查看大部分运行库类的源代码，所以只需要花费1分钟的时间进行研究，你就应该能够自己回答这个问题。 - Andreas

Answer 1

如果新长度小于旧长度，则其时间复杂度为O(1)，在你的情况下，新长度确实小于旧长度。

JDK的源代码可在网上获取，因此您可以自己检查它。以Java 8为例，setLength是在AbstractStringBuilder中实现的。它会执行以下操作：

• 如果新长度小于0，则会出错。
• 确保StringBuilder具有足够的容量来存储新长度（如果您缩短长度，则它将具有足够的容量）。
• 如果您扩展长度（但您没有这样做），则填充0以达到额外的长度。
• 将this.count字段设置为指定的长度。

总结一下：

• 如果您缩短长度，则其时间复杂度为O(1) - 进行一些快速检查，然后进行字段分配。
• 如果您增加长度，但旧容量仍然足够，则其时间复杂度为O(N)，其中N是额外的长度（例如，如果您有一个100长度的构建器，然后将其缩短到10，并且现在将其增加到90，则N将是90-10=80）。
• 如果您增加长度以使容量需要增加，则其时间复杂度为O(N)，其中N是新容量。

- yshavit

---

除了在网上可以获取源代码外，当您安装JDK时也会获得一份拷贝。如果使用一个好的集成开发环境，它将自动使用该拷贝，这样您就可以查看大多数运行时库类的源代码（例如，在Eclipse中，当光标位于类或方法上时，按下F3键即可）。 - Andreas

Answer 2

setLength方法的复杂度与操作（增加或减少）不同。增加操作的复杂度不是O(1)，我认为它是O(n)，因为在此操作中将生成新数组，并且每个未使用的stringbuilder字节都将被替换为'\0'字节。

但是，减少操作的复杂度为O(1)，因为在此操作中只会更改字符数。

StringBuilder类源文件中setLength方法的源代码如下：
http://developer.classpath.org/doc/java/lang/StringBuilder-source.html

 225:   public void setLength(int newLength)
 226:   {
 227:     if (newLength < 0)
 228:       throw new StringIndexOutOfBoundsException(newLength);
 229: 
 230:     int valueLength = value.length;
 231: 
 232:     /* Always call ensureCapacity in order to preserve copy-on-write
 233:        semantics.  */
 234:     ensureCapacity(newLength);
 235: 
 236:     if (newLength < valueLength)
 237:       {
 238:         /* If the StringBuilder's value just grew, then we know that
 239:            value is newly allocated and the region between count and
 240:            newLength is filled with '\0'.  */
 241:     count = newLength;
 242:       }
 243:     else
 244:       {
 245:     /* The StringBuilder's value doesn't need to grow.  However,
 246:        we should clear out any cruft that may exist.  */
 247:     while (count < newLength)
 248:           value[count++] = '\0';
 249:       }
 250:   }

- Taleh Ibrahimli

Answer 3

从文档中可以看到：

设置字符序列的长度。该序列被更改为一个新的字符序列，其长度由参数指定。对于每个小于newLength的非负索引k，如果k小于旧字符序列的长度，则新字符序列中索引k处的字符与旧序列中索引k处的字符相同；否则，它是空字符“\u0000”。换句话说，如果newLength参数小于当前长度，则长度将更改为指定的长度。 如果newLength参数大于或等于当前长度，则会附加足够的空字符（'\u0000'），以使长度成为newLength参数。

newLength参数必须大于或等于0。

我认为是这样的。但我不认为这是时间复杂度的问题。我们在循环中使用StringBuilder而不是String的原因是字符串是不可变的。因此，当我们尝试更改它时，总是会创建一个新的字符串对象。当您更改StringBuilder对象的长度时，不会创建新对象。

- user3437460

---

这个答案是误导性的，因为如果新长度大于底层数组的当前长度，它将需要完全复制先前的数组。我认为@yshavit的答案更准确。 - Dici