这两个示例代码的时间复杂度是否不同，如何？

Question

考虑到招聘过程中的一些问题，一个问题是在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 '_';
}

Answer 1

第二个代码段效率较低。

在第二个代码段中，计算每个字符的出现次数，并返回第一个出现一次的字符。这比调用s.indexOf（s.charAt（i））和s.lastIndexOf（s.charAt（i））效率低，后者只搜索两个匹配项。

您可以轻松地改进第二个片段，使其与第一个片段的行为相同（即，一旦您发现索引处出现s.charAt（i）！=i）。

这就是说，这两个代码段都有相同的渐近运行时间，因为在最坏的情况下，索引和最后索引都需要线性时间，这与第一个代码段的内部循环相同。

另一方面，对于某些输入，第一个代码段比第二个快得多。例如，如果html" target="_blank">字符串的所有字符都相等，则第一个代码段将花费线性时间（因为每次调用时，索引和最后索引都必须只检查字符串的一个字符），但第二个代码段将花费二次时间。

当然，比第一个或第二个片段更有效的实现是使用HashSet来跟踪已经出现的字符。这可以在String的单次迭代中完成，这需要线性时间。

Answer 2

首先，从你的问题中，我意识到快速解释时间复杂度和大哦符号会很好。

引用维基百科：

在计算机科学中，时间复杂度是描述运行算法所需时间的计算复杂度。时间复杂度通常通过计算算法执行的基本操作的数量来估计，假设每个基本操作需要固定的时间来执行。[...]由于算法的运行时间可能因相同大小的不同输入而异，因此通常考虑最坏情况时间复杂度，即给定大小的输入所需的最大时间量。

算法复杂性根据大O表示法中出现的函数类型进行分类。例如，时间复杂度为O（n）的算法。O（n）是一个线性时间算法，对于某些常数alpha，它的时间复杂度为O（n^alpha）

看看这两个代码示例。我们立即注意到一些事情。

1. 在示例1中，代码的大小要小得多。所以我们可能会有更少的操作

让我们做一个小实验。让我们计算在平均糟糕的情况下（第一个非重复字符在中间），当Z的大小=1、10、100和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

在Alogrithm 1中，我们看到复杂性与s的输入大小呈线性相关，特别是与O（n）相关。在算法2中，我们看到它是多项式时间，具体地说是O（n^2）。然而，一旦我们考虑到索引和最后索引的实际成本，这就错了。

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的实现。如果它们在数组中搜索，则会在数组中隐藏循环。在这种情况下（最后一个例子），两种算法的成本变得更加相似。

Algo1: N^2/4 + N/2  + 1
VS
Algo2: N^2/2 + N + 1