搜索重复字符串的复杂性

Question

我有一个任务来查找重复的元素，并写一个方法来返回一个布尔值。

下面的代码是我所拥有的。

import java.util.ArrayList; 
import java.util.List; 

public class DuplicateEle { 
    public static void main(String args[]) { 
     String[] arr = { "hello", "hi", "hello", "howru" }; 
     DuplicateEle de = new DuplicateEle(); 
     for (int i = 0; i < arr.length; i++) { 
      boolean isDup = de.isDuplicate(arr[i]); 
      System.out.println(arr[i]+" is duplicate :" +isDup); 
     } 
    } 

    List<String> dList = new ArrayList<String>(); 

    private boolean isDuplicate(String str) { 
     boolean isDup = false; 
     if (dList.contains(str)) { 
      isDup = true; 
     } else 
      dList.add(str); 
     return isDup; 
    } 

} 

它按预期工作。 输出：

hello is duplicate :false 
hi is duplicate :false 
hello is duplicate :true 
howru is duplicate :false 

我想找到上述代码的时间复杂性。我正在寻找关于如何工作的时间复杂性的教程，如one。

有人可以给我关于上述代码的意见，并帮助我了解时间复杂性如何工作吗？

预先感谢您！

Answer 1

你让你的代码方式太复杂了，使用HashSet<String>，这将保证唯一性，并返回元素是否已经在集合中。

public class DuplicateEle { 
    public static void main(String args[]) { 
     Set<String> seen = new HashSet<>(); 
     String[] arr = { "hello", "hi", "hello", "howru" }; 

     for (String word : arr) { 
     boolean unique = seen.add(word); 
     System.out.printf("%s is duplicate: %b%n", word, !unique); 
     } 
    } 
} 

使用HashSet是非常有效的，因为它会使用散列int的字符串，找到桶，才需要使用equals做一个完整的“昂贵”等于。

Answer 2

可以说，n是要检查的元素的数量，m是最长的单词的大小。所以，你通过一系列元素，并检查每个元素是否在dList中。

在开始时，它是空的，所以随着时间的推移，你添加了元素。所以，问题是，方法contains有多快。如果您查看ArrayList的源代码，您会看到它遍历数组并检查每个元素是否为equal，这是通过从结尾开始检查每个字符来完成的（首先检查它们是否大小相同） 。

所以最坏的情况是所有的元素都是相同的大小，它们在第一个元素上是不同的。因此，在第一个元素中，你什么都不做，所以基本操作计为1.在步骤2中，你做1检查，在步骤3，你做2检查等，并在第n步你做n-1检查包含。所以，你必须：

0+1+2+...+n-1 = n(n-1)/2 

现在，最坏的情况下，每一个元素都是相同的大小，他们在第一要素不同，所以你有大小m的另一个循环。这里，m也可以表示字符串（从结尾）开始的不同char的位置的平均字符串大小或统计期望。

因此，它的O(mn^2)，但如果我们说m有一些随机性，我们可以说它的Ω(n^2)。

但我对你有个好消息。有更快的方法，通过使用HashSet。你只需要一些HashSet的改变DLIST，并把每个元素在里面，你去通过初步名单，所以检查每个元素将在O(1)来完成，这意味着，总体速度会O(n)。