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

Question

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

我理解它的方式是这个操作简单地减少了我的StringBuilder对象的一些私有属性,并且不对字符本身执行任何复制/克隆/复制,因此它是O(1)及时并且应该快速工作.

我对吗？

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是新容量

Answer 2

从文档中：

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

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

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