Set操作的複雜性

這是我在做什麼：
字符串一個=「一些字符串」
String中的兩個=「一些字符串」Set操作的複雜性

我想知道的一切都在字符串中的字符一個和兩個和他們應該按順序排列，因爲他們在字符串之一

我寫了一個Java程序，它通過使用集合執行集合上的集操作。
我想知道什麼是執行一系列操作的複雜性是什麼，是多項式時間或線性時間

我的計劃是在這裏

/* 
* To change this template, choose Tools | Templates 
* and open the template in the editor. 
*/ 

package careercup.google; 

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Iterator; 
import java.util.List; 

/** 
* 
* @author learner 
*/ 
public class CharaterStringsIntersection { 
    private static final String one = "abcdefgabcfmnx"; 
    private static final String two = "xbcg"; 

    public static void main(String args[]){ 
     List<Character> l_one = new ArrayList<Character>(); 
     List<Character> l_two = new ArrayList<Character>(); 

     for(int i=0; i<one.length(); i++){ 
      l_one.add(one.charAt(i)); 
     } 
     for(int j=0; j<two.length(); j++){ 
      l_two.add(two.charAt(j)); 
     } 

     l_one.retainAll(l_two); 

     Iterator iter = l_one.iterator(); 
     while(iter.hasNext()){ 
      System.out.println(" > " + iter.next()); 
     } 
    } 
}

輸出：

run: 
> b 
> c 
> g 
> b 
> c 
> x

來源

2010-10-24 daydreamer

您可以使用LinkedHashSet在保留訂單的同時獲取Set的性能。注意：您只需要在第一個集合中保留訂單，第二個訂單的順序並不重要？你需要保持重複嗎？如果是這樣，第一個集合必須是一個列表，但第二個集合仍然可以是一個集合。 – 2010-10-24 23:44:23

其複雜度爲O（N *（N + M）），其中N = one.length()，M = two.length()。

它工作在以下方式：用於l_one每個字符（有它們的N）它掃描l_two（因爲l_two是ArrayList，掃描是線性的，所以它需要O（M）步驟，請參閱[1] ），並從l_one中刪除項目（如果需要從ArrayList中刪除，參見[1]），所以你得到O（N *（N + M））。

可以通過使用LinkedList爲l_one降低複雜度爲O（N * M）（由於從LinkedList去除是O（1），參見[2]），並且進一步它低到O（N *日誌（ M））通過使用TreeSet爲l_two（因爲在TreeSet中搜索需要O（log（M）），參見[3]）。

參考文獻：

其他所有操作都以線性時間（ArrayList javadoc）
所有操作的執行是可以預期的雙向鏈表，（運行LinkedList javadoc）
此實現爲基本操作提供了有保證的log（n）時間成本（add， remove和contains）（TreeSet javadoc）

來源

2010-10-24 22:07:38 axtavt

保證/指定Java收集方法的複雜性（以STL提供保證的方式）？我在Javadocs裏找不到任何東西...... – 2010-10-24 22:19:15

@Oli：我添加了參考文獻。 – axtavt 2010-10-24 22:29:40

哦，文檔說明了這一點！謝謝，我看不到樹木... – 2010-10-24 22:34:05

您使用了錯誤的收集你的目的..

既然你是用普通ArrayList做的複雜性會不會好，我不知道內部的實現，但我猜想它是二次的（因爲它必須滾動兩個列表），除非Java在內部將交集之前將兩個列表轉換爲集合。

您應該Set接口（here）開始，並選擇其收集更適合您的需求，我認爲一個HashSet（恆定時間）或TreeSet（對數，但能保持自然順序）將是最好的解決方案。

來源

2010-10-24 22:07:42 Jack

我想你要問的更重要的問題是retainAll（）函數的複雜性。假設沒有哈希或快速查找，我會假設時間複雜度爲O（n^2）。一個循環迭代列表和一個循環來比較每個項目。

來源

2010-10-24 22:08:58

Something告訴我這是一個面試問題;）我認爲你應該開始考慮其他數據結構。如果你使用散列，這個問題可能是O（n） – 2010-10-24 22:10:24

簡言之：

ArrayList.add()是O(1)。
ArrayList.retainAll(other)是O(N1 * N2)其中N1是this和N2尺寸的other大小。（實際成本取決於保留，以除去元素的元素比。）
iter.hasNext()和iter.next()是O(1)用於ArrayList迭代器。

這一切都是你所期望的基礎上，精神上建模一個ArrayList作爲Java數組。

來源

2010-10-24 23:09:20

Set操作的複雜性

回答

相關問題