回文递归算法的时间复杂度

Question

下面检查给定输入是否为回文的代码的时间复杂度是多少？

public boolean isPalindromeRecursion(String input, int first, int last) {
    if (input.charAt(first) != input.charAt(last)) {
        return false;
    } else if (first >= last) {
        return true;
    }
    return isPalindromeRecursion(input, first + 1, last - 1);
}

Answer 1

你的算法的时间复杂度是：

1. 严格来说 - O(n/2);
2. 用渐近分析语言说话-O(n)，因为constant factors are disregarded when we use Big O analysis, and it's good他们被忽略了。