java - 回文算法的时空复杂度

Question

Java 中寻找回文的下列代码的时间和空间复杂度是多少:

    public static boolean isPalindrome(String str) {
        return str.equals(new StringBuilder(str).reverse().toString());
    }

我知道 reverse() 是 O(n)。 toString() 也是 O(n)。等于也是 O(n)。这是否意味着这段代码是 O(n) 的？

至于空间复杂度，需要创建一个StringBuilder。我不确定它被转换成字符串后会发生什么。 Java 是否为转换为字符串的 StringBuilder 分配空间，然后忘记 StringBuilder(允许它被垃圾收集器拾取)？

谢谢!

------------ 编辑------------

我想知道调用 isPalindrome 后在堆栈上创建了什么。与

相比，它在空间方面的效率如何？

谢谢!不过，我仍然不太了解这段代码在空间方面的效率如何。堆栈上究竟会创建什么？与

相比，它的效率如何(就空间而言)

public boolean palindrome2(String str) {    
        int n = str.length();
        for( int i = 0; i < n/2; i++ )
            if (str.charAt(i) != str.charAt(n-i-1)) return false;
        return true;    
}

Answer 1

假设所有这些操作确实是 O(n)，我会说你是对的:O(n) + O(n) + O(n) = 3 * O(n)(或 O(3n)，如果你愿意的话)，则属于 O(n) 类别。

StringBuilder 的内容 - 您创建了一个匿名实例，并且在方法 isPalindrome 结束后，没有对该对象的引用，因为它的作用域仅为此方法。所以是的，它最终会被垃圾收集器处理。很可能不会立即生效，但我认为这与您无关。