搜索重複字符串的複雜性

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