isPalindrome() 的时间复杂度 O()
https://stackoverflow.com/questions/1318545
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我有这个方法，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)？这是正确的，如果不是的话，它是什么以及如何计算出来的。
另外，为了提高效率，将字符存储在临时字符串中是否会更好？
解决方案
给定的代码似乎是通过检查字符“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;
}
其他提示
这只是O（N）。
话说O（N + 3）是没有太大意义。 - 恒定的因素被忽略
当它发现不符，您可以使它更快的突破：
bP = false;
break;
（这并不是说，改变的事实，它的O（N），但它会加速它在大多数情况下最高。）
这是不正确的：
此代码检查字符串的字符以看它是否是相同的其前一个
它检查在开始字符在端匹配的，所以，换句话说，它是一个幼稚回文检查器。
另一个会加速循环，直到s.length()/2 - 否则你做的所有比较两次的字符串是回文
这很可能是 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 应用程序编程接口 并且没有错误处理，正如评论中指出的那样。它纯粹是为了证明通过肮脏的技巧可以获得的理论上的性能改进。
从字符串复制数组时会产生一些开销，因为字符串类在内部进行了防御性复制。
如果我们直接从字符串中获取原始的 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
有O（N）。你是做ň比较，其中N = s.length（）。每个比较花费O（1）时间，因为它是一个单独的字符进行比较。
3不要紧，因为渐近符号只关心最高阶项。
下面是具有两个相对的指针的另一个解决方案：
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;
}
在复杂性又是 0 的（名词的）。
去多一点到的详细信息：假设每个操作成本1个单位。比较，分配，算术运算，函数调用每个成本1个单位。因此，在最坏的情况下（是isPalindrome回文）的s成本的呼叫需要，例如：
4 + n/2 · (3 + 4) + 1
= 5 + n/2 · 7
= 5 + 7/2 · n
和由于省略了常数因子（此处5 + 7/2），我们最终用5 + 7/2·名词∈ 0 的（ ñ）。
首先，不能有对于这个问题，其中“最坏情况”复杂度比O(N)对于任意输入串更好单线程溶液。简单地说，任何算法必须看在最坏的情况下，字符串中的每个字符。在理论上可以提高使用硬件并行O(N);即对串的不同部分工作的处理器的一个可扩展的无限数目。在实践中，这将是很难取得任何加速的。发送所述输入字符串（或相关部分），以每个处理器的费用将是“O（N）”，除非有一些解决方案，我不知道。
其次，你可以看到O(N)行为是不是最终答案。你还需要考虑乘法常数为N - >无穷大，并且对于N更小的值的较小者术语
三，@dfa说，这是不是你的企业微优化。他是在正确的轨道上，但我不认为这是很清晰切割为。 IMO，它是时间的浪费微优化除非1）你的应用程序的确实需要尽可能快地运行，并且2）你的应用程序的分析表明，该特定计算的确实的是显著瓶颈。
最后，微优化，使一个节目更快对一个特定的硬件平台/ JIT编译器，可以使其为较慢另一个。复杂的微优化代码为JIT编译器生成高效的代码更难。如果你使用反射来访问的（说）String类的内部，你的代码实际上可能会失败，在某些平台上。 （在Java类库规范没有说字符串中有所谓的“值”是一个char[]私有字段!!!）
那么首先，这个方法应该做什么？
我猜：判断一个字符串是否是一个 回文.
很明显，你将无法在 O(N) 下得到它：
O(N+3) == O(N)
另一个问题是，这是最有效的解决方案吗？也许不会。
改进空间：
把它切成两半。您检查所有字符两次（就像 Michiel Buddingh 建议的那样）。
预先获取字符数组。这可以让你省去一些内部发生的索引检查
chatAt().
所有其他操作， charAt() 和 length(), ，对于标准 String 实现来说是 O(1)。
首先改进：你可以打破，一旦你找到一个非匹配，权
假设在循环的操作可以在恒定的时间来执行，所述复杂度是O（N）。 由于“大O”符号措施增长，而不是纯粹的速度，持续性因素可以忽略不计。这就给我们的结论是O（N + 3）等于O（N）。
大O 复杂性是始终没有costants（由于用于N-> OO，它们是不重要）。所以，你的时间复杂度简单地O(n)。
此外，使这个更有效，这将是很好的字符存储在临时字符串？
这是不是你的工作。 JIT编译器会处理这条微优化你。
可以通过在停止（ⅰ==（s.length（）/ 2）+1）切断的功能的复杂性中的一半。这是不是在大O方面有关，但它仍然是一个相当不错的收益。
或者，你可以简单地做
def isPalindrome?(x)
return x == x.reverse
end
这仍然是O（n）的时间复杂度。
