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;
}
最佳答案
假设所有这些操作确实是 O(n),我会说你是对的:O(n) + O(n) + O(n) = 3 * O(n)(或 O(3n),如果你愿意的话),则属于 O(n) 类别。
StringBuilder
的内容 - 您创建了一个匿名实例,并且在方法 isPalindrome
结束后,没有对该对象的引用,因为它的作用域仅为此方法。所以是的,它最终会被垃圾收集器处理。很可能不会立即生效,但我认为这与您无关。
关于java - 回文算法的时空复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32427217/