Space 递归算法的复杂度

Question

我有一个递归算法可以在 Java 中找到回文。如果给定的字符串是回文，它应该 return 为真。否则为假。该方法使用子串法，求复杂度比较麻烦

这是我的算法：

static boolean isPalindrome (String str) {
    if (str.length() > 1) {
        if (str.charAt(0) == (str.charAt(str.length() - 1))) {
    if (str.length() == 2) return true;
            return isPalindrome(str.substring(1, str.length() - 1));
        }
        return false;
    }
    else {
        return true;
    }
}

这个算法的 space 复杂度是多少？

我的意思是，当我调用方法 substring() 时，它是否一直在创建一个新字符串？ substring 方法在 Java 中实际上做了什么？

Answer 1

旧版本 Java (mainly in Java 6 and before)*, substring returned a new instance that shared the internal char array of the longer string (that is nicely illustrated here)。然后 substring 有时间和 space 复杂度 O(1).

较新的版本使用 String 的不同表示，它不依赖于共享数组。相反，substring 分配一个刚好需要大小的新数组，并从较长的字符串中复制内容。那么 substring 的时间和 space 复杂度为 O(n).

_{*实际上，更改是在 Java 7.}

的更新 6 中引入的

Space 递归算法的复杂度

Space complexity of a recursive algorithm

java

algorithm

recursion

space-complexity