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)的事实,但在大多数情况下它会加速它.)

事实并非如此:

此代码检查字符串的字符,以查看它是否与之前的字符相同

它会检查开头的字符是否与最后的字符匹配,换句话说,它是一个天真的回文检查器.

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

Answer 2

给定的代码似乎是通过检查字符"N"是否与字符"length-N"相同来检查字符串是否是回文结构.如前所述,您可以通过提高效率

• 只检查上半场
• 一找到不匹配就会爆发(返回false)

对于那些建议,我补充一下

• 每次循环都不会重复计算s.length(),因为它不会改变.

鉴于这一切:

boolean isP(String s) {
  int l = s.length();
  int l2 = l/2;
  int j = l - 1;
  for(int i=0; i<l2; i++) {
    if(s.charAt(i) != s.charAt(j)) {
        return false;
    }
    j--;
  }
  return true;
}

Answer 3

这很可能是Java中最有效的实现:

    public static boolean isP(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < (chars.length / 2); i++) {
            if (chars[i] != chars[(chars.length - i - 1)])
                return false;
        }
        return true;
    }

优点:

• 第一眼看到差异的回报.
• 使用直接char []访问来避免在charAt中进行的aboundary检查
• 只迭代字符串的一半,而不是整个字符串.

与所有其他提出的解决方案一样,它仍然是O(N).

我只是测量了所提出的解决方案的时间,以获得非常大的字符串(以纳秒为单位):

 Aran:           32244042
 Andreas:        60787894
 Paul Tomblin:   18387532

首先,上述测量是使用客户端VM完成的.因此,计算i < (chars.length / 2)不作为常数内联.使用-server Vm参数可以得到更好的结果:

 Aran:           18756295
 Andreas:        15048560
 Paul Tomblin:   17187100

为了推动它有点极端:

首先要警告:不要在任何您打算使用/运输的程序中使用此代码.

它包含隐藏的错误,并且不遵守Java API并且没有错误处理,如评论中所指出的那样.它纯粹是为了证明通过肮脏技巧可以获得的理论性能改进.

从字符串复制数组时会有一些开销,因为字符串类在内部产生防御性副本.

如果我们直接从字符串中获取原始的char [],我们可以挤出一些性能,代价是对字符串使用反射和unsave操作.这让我们再获得20%的表现.

public static boolean isPReflect(String s) {
    char[] chars = null;
    try {
        final Field f = s.getClass().getDeclaredField("value");
        f.setAccessible(true);
        chars = (char[]) f.get(s);
    }
    catch (IllegalAccessException e) {
    }
    catch (NoSuchFieldException e) {
    }

    final int lenToMiddle = chars.length / 2;
    for (int i = 0; i < lenToMiddle; i++) {
        if (chars[i] != chars[(chars.length - i - 1)]) 
            return false;
    }
    return true;
}

时报:

 Aran:           18756295
 Andreas1:       15048560
 Andreas2:       12094554
 Paul Tomblin:   17187100