java - isPalindrome() 的时间复杂度 O()

Question

我有这个方法，isPalindrome()，我正在尝试找出它的时间复杂度，并更有效地重写代码。

boolean isPalindrome(String s) {
    boolean bP = true;
    for(int i=0; i<s.length(); i++) {
        if(s.charAt(i) != s.charAt(s.length()-i-1)) {
            bP = false;
        }
    }
    return bP;
}

现在我知道这段代码会检查字符串的字符，看它是否与之前的相同，如果相同，则不会更改 bP。

我想我知道操作是 s.length()、s.charAt(i) 和 s.charAt(s.length()-i-!))。

我认为时间复杂度为 O(N + 3)？这是正确的，如果不是，它是什么以及如何计算出来的。

另外，为了提高效率，将字符存储在临时字符串中会好吗？

Answer 1

这只是 O(N)。

说 O(N+3) 并没有真正意义 - 常数因子被忽略。

您可以通过在发现不匹配时中断来使其更快:

bP = false;
break;

(并不是说这改变了它是 O(N) 的事实，但在大多数情况下它会加快它的速度。)

这不是真的:

this code checks the string's characters to see whether it is the same as the one before it

它检查开头的字符是否与结尾的字符匹配，所以换句话说，它是一个天真的 palindrome检查器。

另一个加速将循环直到 s.length()/2 - 否则你将对回文字符串进行两次所有比较。