Java StringBuilder.setLength() - 时间复杂度是 O(1) 吗？

Question

我打算对 StringBuilders 中的最后一个字符执行大量删除操作。使用 sb.setLength(sb.length() - 1); 的解决方案对我来说看起来不错。但是，由于这些删除将处于循环中，我需要知道它的复杂性。

我的理解是这个操作只是减少了我的 StringBuilder 对象的一些私有属性并且不执行任何 copying/cloning/duplicating 字符本身，因此它是 O(1) 时间并且应该工作快.

我说得对吗？

Answer 1

如果新长度小于旧长度，则为 O(1)，在您的情况下。

JDK的源码网上有，大家可以自行查看。以Java8为例，setLength在AbstractStringBuilder中实现。它做了一些事情：

如果新长度 < 0 则出错
确保 StringBuilder 有足够的容量来容纳新的长度（如果您要缩短长度，它会这样做）
如果您要延长长度（您没有），则为额外长度填写 0
将 this.count 字段设置为您指定的长度

综合起来：

如果您要缩短长度，这是 O(1) — 一些快速检查，然后是字段分配。
如果你增加长度，但旧容量仍然足够，那么它是 O(N)，其中 N 是额外的长度（例如，如果你有一个 100 长度的构建器，然后缩短它增加到 10，现在增加到 90，那么 N 将是 90-10=80)
如果增加长度导致容量需要增加，则为 O(N)，其中 N 是新容量

Answer 2

来自文档：

Sets the length of the character sequence. The sequence is changed to a new character sequence whose length is specified by the argument. For every nonnegative index k less than newLength, the character at index k in the new character sequence is the same as the character at index k in the old sequence if k is less than the length of the old character sequence; otherwise, it is the null character '\u0000'. In other words, if the newLength argument is less than the current length, the length is changed to the specified length. If the newLength argument is greater than or equal to the current length, sufficient null characters ('\u0000') are appended so that length becomes the newLength argument.

The newLength argument must be greater than or equal to 0.

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

Answer 3

setLength 的复杂度与操作不同（增加或减少） increase操作的复杂度不是O(1)，我认为是O(n)，因为，在这个操作中会生成新的数组，stringbuilder的每个未使用的字节被替换为'\0'byte

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

StringBuilder中有setLength方法的源码class源码文件
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 '[=10=]'.  */
 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++] = '[=10=]';
 249:       }
 250:   }

Java StringBuilder.setLength() - 时间复杂度是 O(1) 吗？

Java StringBuilder.setLength() - is time complexity O(1)?

java

big-o

time-complexity