StringBuilder反向方法的时间复杂度

Question

我想求StringBuilder反向方法的时间复杂度。 这里是反向方法的源代码：

 public AbstractStringBuilder reverse() {
        boolean hasSurrogate = false;
        int n = count - 1;
        for (int j = (n-1) >> 1; j >= 0; --j) {
            char temp = value[j];
            char temp2 = value[n - j];
            if (!hasSurrogate) {
                hasSurrogate = (temp >= Character.MIN_SURROGATE && temp <= Character.MAX_SURROGATE)
                    || (temp2 >= Character.MIN_SURROGATE && temp2 <= Character.MAX_SURROGATE);
            }
            value[j] = temp2;
            value[n - j] = temp;
        }
        if (hasSurrogate) {
            // Reverse back all valid surrogate pairs
            for (int i = 0; i < count - 1; i++) {
                char c2 = value[i];
                if (Character.isLowSurrogate(c2)) {
                    char c1 = value[i + 1];
                    if (Character.isHighSurrogate(c1)) {
                        value[i++] = c1;
                        value[i] = c2;
                    }
                }
            }
        }
        return this;
    }

这是文档的链接：文档 时间复杂度是多少？

有什么方法可以更有效地执行字符串的还原吗？

Answer 1

恢复可变字符串意味着重新定位至少一半的字符（如果就地执行），因此复杂度为 O(n)。您发布的代码有两个循环，确认它是 O(n)。

从更理论上讲，整个

StringBuilder

实现可以致力于 O(1) 反转，这样您只需设置一个标志，然后所有方法通过从前到后或从后解释数组内容来尊重它-到前面。我说“理论上”是因为仅仅为了 O(1) 字符串反转而增加一切的复杂性并使其变慢是没有意义的。