考虑到招募过程中的一些问题，问题是在Java中从给定字符串中找到第一个不重复的字符。以下是两个示例代码，其中第一个能够通过所有测试用例，但由于时间复杂性，第二个在少数测试用例中失败。由于我是算法和复杂性分析的新手，有人能帮助我了解这两种代码的时间复杂性是否不同以及如何不同吗？
示例代码1:
public static char firstNonRepeatingCharater(String s) {
for(int i=0;i<s.length(); i++) {
if(s.indexOf(s.charAt(i)) == s.lastIndexOf(s.charAt(i))) {
return s.charAt(i);
}
}
return '_';
}
示例代码2:
public static char firstNonRepeatingCharater(String s) {
for(int i=0;i<s.length(); i++) {
int count = 0;
for(int j=s.length()-1;j>=0; j--) {
if(s.charAt(i) == s.charAt(j)) {
count++;
}
}
if(count == 1) {
return s.charAt(i);
}
}
return '_';
}
计算复杂性
首先，从你的问题中，我意识到快速解释time complexity和big oh notation会很好。
引用自维基百科：
在计算机科学中，时间复杂性是计算的描述运行算法。时间复杂性通常通过计算算法执行的基本操作数，假设每个基本操作都需要固定的时间表演[…]由于算法的运行时间可能在通常考虑最坏情况下的时间复杂性，这是给定的输入所需的最大时间量大小
大O符号
算法复杂性根据函数出现在大O符号中。例如，一个算法时间复杂度为O(n)。O(n)是线性时间算法和一个时间复杂度为O(n^alpha)的常数算法alpha>1是一个多项式时间算法。
关于两个代码示例
请看一下这两个代码示例。我们立刻注意到了一些事情。
- 在示例1中，代码的大小要小得多。所以我们可能会减少手术
- 然而，更重要的是，我们注意到第二个示例中有一个嵌套的for循环。第一个样本没有。这并不一定会降低方法中代码的隐藏成本
让我们做一个小实验。当size of Z is = 1, 10, 100, and 1000时，让我们计算在平均糟糕的情况下(第一个非重复字符位于中间)所需的操作数。
注意：在这个例子/思想实验中，我将把每一行评估为成本1的操作。这是一个粗略的简化请原谅在计算操作次数时的任何遗漏。
Algorithm 1: (size of s, lines executed)
-
1, 3
10, (2*5)+1 = 11
100, (2*50)+1 = 101
1000, (2* 500) + 1 = 1001
Total = (2* N/2 ) + 1
我们看到，执行的结果数量与初始输入大小线性相关。
Algorithm 2: (N = size of s, lines executed)
-
1, 7
10, 2(5*5) + 2
100, 2(50*50) + 2
1000, 2(500*500) + 2
Total = ((N/2) *2 + 2*(N/2)*(N/2) + 2
在图1中，我们看到复杂性与s的输入大小线性相关，特别是O(n)。在算法2中，我们看到它是多项式时间，特别是O(n^2)。然而，一旦我们考虑到indexOf和lastIndexOf的实际成本，这就变得错误了。
添加indexOf和LastIndexOf的成本
Let n=Size of the String S
算法1：(粗略估计的操作次数)
for(int i=0;i<s.length(); i++) // - N/2
if(s.indexOf(s.charAt(i)) == s.lastIndexOf(s.charAt(i))) { // ~ worst case = (N/2 + N/2) * N/2
return s.charAt(i); // 1 operation
Total = N/2 + (N/2 + N/2)*N/2 +1
= N^2/2 + N/2 + 1
算法2：(粗略估计的操作次数)
for(int i=0;i<s.length(); i++) { // - executed N/2 times
int count = 0; // - executed N/2 times
for(int j=s.length()-1;j>=0; j--) { // Executed (n/2 * n/2 )
if(s.charAt(i) == s.charAt(j)) { // Executed (n/2 * n/2 )
count++; // Executed 1 time
}
}
if(count == 1) { //Evaluated N/2 times
return s.charAt(i); // Executed 1 time
}
}
return '_';
Total = N/2 + N/2 + 2(N/2*N/2) + 1
= N^2/2 + N + 1
注意：我做了不少简化。我还假设非重复字符将位于字符串(字符数组)的中心(n/2)。要注意的要点是，执行的操作的估计数量随着大小的增加而增加。上面的例子旨在证明这一点。并非100%准确。
此外，评论中指出的整个结果/参数是我们如何考虑indexOf和lastIndexof的。我们是否将其视为单一操作？还是我们认为它们是N/2操作？它还取决于indexOf和lastIndexOf的实现。如果这些人在数组中搜索，那么他们将for loops隐藏在里面。在他们这样做的情况下(最后一个例子)，两种算法的成本变得更加相似。
Algo1: N^2/4 + N/2 + 1
VS
Algo2: N^2/2 + N + 1
第二个片段的效率较低。
在第二个代码段中，计算每个字符的出现次数，并返回第一个出现一次的字符。这比调用s.indexOf(s.charAt(i))和s.lastIndexOf(s.charAt(i))效率低，后者只搜索两次出现。
您可以很容易地改进第二个代码段，使其行为与第一个代码段相同(即，一旦在索引中发现s.charAt(i)的出现！=i，就脱离内部循环)。
也就是说，两个片段具有相同的渐近运行时间，因为在最坏的情况下，indexOf和lastIndexOf都可能需要线性时间，这与第一个片段的内部循环相同。
另一方面，对于某些输入，第一个片段比第二个片段快得多。例如，如果String的所有字符都相等，则第一个片段将花费线性时间(因为每次调用indexOf和lastIndexOf时，它们都必须只检查String的一个字符)，但第二个片段将耗费二次时间。
当然，比第一个或第二个片段更有效的实现是使用HashSet来跟踪已经出现的字符。这可以在String的一次迭代中完成，这将需要线性时间。