6

我有这个方法，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)？这是正确的，如果不是，它是什么以及如何计算出来的。

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

4

12 回答 12

16

这只是 O(N)。

说 O(N+3) 并没有真正的意义——常数因素被忽略了。

当它发现不匹配时，您可以通过打破它来使其更快：

bP = false;
break;

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

这不是真的：

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

它检查开头的字符是否与结尾的字符匹配，因此换句话说，它是一个简单的回文检查器。

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

于 2009-08-23T13:32:40.993 回答
13

给定的代码似乎是通过检查字符“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;
}
于 2009-08-23T13:37:31.847 回答
6

这很可能是 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 中进行的边界检查
  • 仅迭代一半字符串，而不是完整字符串。

与所有其他提议的解决方案一样，它仍然是 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
于 2009-08-23T14:02:04.343 回答
4

这是另一个具有两个相反指针的解决方案：

boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j && s.charAt(i) == s.charAt(j)) {
        ++i;
        --j;
    }
    return i >= j;
}

复杂度再次为O ( n )。

更详细一点：假设每次操作花费 1 个单位。比较、赋值、算术运算、函数调用每个花费 1 个单位。因此，在最坏的情况下调用isPalindrome成本（s是回文）例如：

  4 + n/2 · (3 + 4) + 1
= 5 + n/2 · 7
= 5 + 7/2 · n

由于省略了常数因子（此处为 5 + 7/2），我们最终得到 5 + 7/2 · n ∈ O ( n )。

于 2009-08-24T09:41:01.267 回答
3

它开着）。您正在进行 N 次比较，其中 N=s.length()。每次比较都需要 O(1) 时间，因为它是单个字符比较。

+3 无关紧要，因为渐近符号只关心最高阶项。

于 2009-08-23T13:33:29.307 回答
2

首先，对于这个问题，不可能有一个单线程解决方案，其中“最坏情况”的复杂性优于O(N)任意输入字符串。简单地说，任何算法都必须在最坏的情况下查看字符串中的每个字符。从理论上讲，您可以改进O(N)使用硬件并行性；即在字符串的不同部分上工作的处理器数量可以无限扩展。在实践中，很难实现任何加速。将输入字符串（或相关部分）发送到每个处理器的成本将是“O(N)”，除非有一些我不知道的解决方案。

其次，正如你所看到的，O(N)行为并不是最终的答案。您还需要将乘法常数考虑为 N -> 无穷大，而较小的项则代表较小的 N 值。

第三，@dfa 说微优化不是你的事。他走在正确的轨道上，但我不认为它是如此明确。IMO，除非 1）您的应用程序确实需要尽可能快地运行，并且 2）您对应用程序的分析表明这种特定的计算确实是一个重要的瓶颈，否则微优化是浪费时间。

最后，对于一个特定的硬件平台/JIT 编译器，使程序更快的微优化可能会使另一个程序变慢。JIT 编译器更难为复杂的微优化代码生成有效的代码。如果您使用反射来访问（例如）String 类的内部，您的代码实际上可能在某些平台上失败。（Java 类库规范中没有任何内容说 String 有一个名为“value”的私有字段，它是一个char[]!!!）

于 2009-08-23T23:14:43.687 回答
1

那么首先，该方法应该做什么？

我的猜测：确定一个字符串是否是回文。

很明显，你将无法在 O(N) 下得到它：

O(N+3) == O(N)

另一个问题是，它是最有效的解决方案吗？也许不吧。

改进空间：

  1. 把它切成两半。您检查所有字符两次（如 Michiel Buddingh 建议的那样）。

  2. 预先获取字符数组。这样可以省去一些发生在内部的索引检查chatAt()。

所有其他操作charAt()和length()，在标准 String 实现中都是 O(1)。

于 2009-08-23T13:35:54.780 回答
0

第一个改进：一旦你找到一个不匹配的，你就可以打破，对吧？

于 2009-08-23T13:32:39.027 回答
0

您可以通过在 (i == (s.length() / 2)+1) 处停止将函数的复杂性减半。它在 Big O 方面无关紧要，但它仍然是一个相当不错的收益。

于 2009-08-23T13:34:04.657 回答
0

大 O复杂度总是没有成本（因为对于 N->oo，它们并不重要）。所以你的时间复杂度很简单O(n)。

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

这不是你的工作。JIT 编译器将为您处理这种微优化。

于 2009-08-23T13:35:10.710 回答
0

假设循环中的操作可以在恒定时间内执行，复杂度为 O(N)。由于“Big-O”表示法衡量的是增长，而不是纯粹的速度，因此可以忽略常数因素。这给我们留下了 O(N+3) 等于 O(N) 的结论。

于 2009-08-23T13:36:36.870 回答
0

或者你可以简单地做

def isPalindrome?(x)
 return x == x.reverse
end

这仍然是 O(n) 时间复杂度。

于 2013-05-11T15:06:13.523 回答