搜索重複字符串的複雜性

-5

我有一個任務來查找重複的元素，並寫一個方法來返回一個布爾值。搜索重複字符串的複雜性

下面的代碼是我所擁有的。

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。

有人可以給我關於上述代碼的意見，並幫助我瞭解時間複雜性如何工作嗎？

預先感謝您！

來源

2017-10-11 lr14

只是使用你給的鏈接。他們解釋了一切。@lexicore愛的鏈接：D – sheplu

@lexicore：不知道我是否理解這一點。推理如？關於任務更具體？ – lr14

@ lr14你向我們投擲任務，你甚至有一個指導如何做到這一點，然後你要求「投入」和「幫助我理解」。如果有人坐下來幫助你閱讀該指南並將其應用於你的任務，你期望什麼？不會發生。如果您真的嘗試應用您所鏈接的指南中所寫的內容，然後在您的問題中寫下您的推理，並詢問是否有人可以發現錯誤，那麼您可能會得到一些實際幫助。但現在你只要求我們爲你做功課。 – lexicore

你讓你的代碼方式太複雜了，使用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做一個完整的「昂貴」等於。

來源

2017-10-11 07:59:47

瞭解。謝謝！！你還可以發佈一些教程來更好地理解時間複雜性嗎？ – lr14

可以說，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)。

來源

2017-10-11 07:47:43

感謝您詳細解釋Arraylist的時間複雜性。如果有的話，你也可以發佈一些複雜的教程鏈接。 – lr14

那麼，你應該首先研究一點數學，準確地說，序列和系列。試試這個https://www.codecademy.com/en/courses/big-o/0/1。它應該給你一些實際的經驗來理解算法的複雜性。但是，最好是閱讀一些關於這個主題的書籍，因爲這是複雜的，並應用了大量的數學，在一些網絡教程中被覆蓋。我推薦這本書：Steve S. Skiena的「算法設計手冊」。 –

這很有幫助。將研究它。謝謝！ – lr14

搜索重複字符串的複雜性

回答

相關問題