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

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

我刚刚测量了一个非常大的字符串所提供的解决方案的时间（时间以纳秒为单位）：

 Aran:           32244042
 Andreas:        60787894
 Paul Tomblin:   18387532

首先，上面的测量是使用客户端虚拟机完成的。因此计算 i < (chars.length / 2) 未作为常量内联。 使用 -server Vm 参数给出了更好的结果：

 Aran:           18756295
 Andreas:        15048560
 Paul Tomblin:   17187100

稍微极端一下：

---

首先警告一句：不要在您打算使用/发布的任何程序中使用此代码。

---

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

从字符串复制数组时会产生一些开销，因为字符串类在内部进行了防御性复制。

如果我们直接从字符串中获取原始的 char[] ，我们可能会降低一些性能，但代价是对字符串使用反射和取消保存操作。这让我们的性能又提高了 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

Answer 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)。

Answer 5

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

+3 并不重要，因为渐近符号只关心最高阶项。

Answer 6

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

其次，正如您所看到的，O(N) 行为并不是最终的答案。您还需要将乘法常数视为 N ->无穷大，以及较小的 N 值。

第三，@dfa 说微观优化不是你的事。他走在正确的道路上，但我认为事情没有那么明确。 IMO，微优化是浪费时间，除非 1) 您的应用程序确实需要尽可能快地运行，并且 2) 您对应用程序的分析表明此特定计算确实< /em> 是一个重要的瓶颈。

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

Answer 7

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

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

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

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

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

改进空间：

1. 将其减半。您检查所有字符两次（就像 Michiel Buddingh 建议的那样）。

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

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

Answer 8

第一个改进：一旦发现不匹配就可以破解，对吧？

Answer 9

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

Answer 10

Big O 复杂度总是没有常量（因为对于 N->oo，它们并不重要） 。所以你的时间复杂度只是O(n)。

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

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

Answer 11

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

Answer 12

或者你可以简单地这样做

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

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