從數字列表生成所有唯一對，n選擇2

我有一個元素列表（我們說整數），我需要做所有可能的2對比較。我的方法是O（n^2），我想知道是否有更快的方法。這裏是我在java中的實現。從數字列表生成所有唯一對，n選擇2

public class Pair { 
public int x, y; 
public Pair(int x, int y) { 
    this.x = x; 
    this.y = y; 
} 
} 

public List<Pair> getAllPairs(List<Integer> numbers) { 
List<Pair> pairs = new ArrayList<Pair>(); 
int total = numbers.size(); 
for(int i=0; i < total; i++) { 
    int num1 = numbers.get(i).intValue(); 
    for(int j=i+1; j < total; j++) { 
    int num2 = numbers.get(j).intValue(); 
    pairs.add(new Pair(num1,num2)); 
    } 
} 
return pairs; 
}

請注意，我不允許自行配對，所以應該有（（N（N + 1））/ 2） - n個可能的對。我目前的工作，但隨着n的增加，它是讓我難以忍受的長時間獲得配對。有什麼辦法可以將上面的O（n^2）算法轉化爲次平方？任何幫助表示讚賞。順便說一下，我也嘗試了下面的算法，但是當我基準測試時，憑經驗來看，它的表現比我上面的要糟糕。我曾認爲通過避免內部循環會加快速度。下面的算法不應該更快嗎？我會認爲這是O（n）？如果沒有，請解釋並告訴我。謝謝。

public List<Pair> getAllPairs(List<Integer> numbers) { 
int n = list.size(); 
int i = 0; 
int j = i + 1; 
while(true) { 
    int num1 = list.get(i); 
    int num2 = list.get(j); 
    pairs.add(new Pair(num1,num2)); 

    j++; 

    if(j >= n) { 
    i++; 
    j = i + 1; 
    } 

    if(i >= n - 1) { 
    break; 
    } 
} 
}

來源

2012-02-26 Jane Wayne

你不能讓它子二次，因爲正如你所說 - 輸出本身是二次的 - 爲了創建它，你至少需要#elements_in_output ops。

但是，你可以做的飛行一些「作弊」創建列表：
您可以創建一個類CombinationsGetter實現Iterable<Pair>，並執行其Iterator<Pair>。通過這種方式，您將能夠即時迭代元素，而無需首先創建列表，這可能會減少應用程序的延遲。

注意：它仍然是二次的！動態生成列表的時間將分佈在更多操作之間。

編輯： 另一種解決方案，這是更快然後天真的方法 - 是多線程。
創建幾個線程，每個線程都會獲得數據的「切片」 - 並生成相關對，並創建其自己的部分列表。
稍後 - 您可以使用ArrayList.addAll()將這些不同的列表轉換爲一個。
注意：雖然複雜性是stiil O(n^2)，它可能會快得多 - 因爲成對的創建是並行完成的，並且ArrayList.addAll()實現得更高效，然後平凡地插入一個元素。

EDIT2： 你的第二個代碼仍然是O(n^2)，即使它是一個「單環」 - 環本身將重複O(n^2)倍。看看你的變量i。它只在j==n時增加，並且它在執行時將j減少回i+1。因此，它將導致n + (n-1) + ... + 1迭代，並且這是sum of arithmetic progression，並使我們回到預期的O(n^2)。

因爲我們正在嘗試創建O（n^2）個不同的對象，所以我們無法改進O（n^2）。

來源

2012-02-26 12:35:43 amit

我發佈了一個不同的版本來獲得配對。它只有1個循環。你能幫我回答我的問題嗎？這是第二個算法O（n）？我同意你的建議（即時創建和多線程）。動態創建不會太難實現，但多線程可能會以較不優雅的代碼/編碼爲代價而更快。它可能會更慢，如果我開始傳遞巨大的名單（我想這樣做）。 – 2012-02-26 15:39:25

@JaneWayne：你不能創建所有需要的對，然後'O（n^2）'。我編輯了答案，對你的第二個實現進行了具體分析，但無論你做什麼 - 創建'O（n^2）'Pair'對象，都需要'O（n^2）'ops。 – amit 2012-02-26 16:12:25

謝謝。我一直在努力找到一本關於算法分析的不流淚的書（不是大多數大學使用的大型精裝書）。如果您有任何建議，請讓我知道。 – 2012-02-26 16:38:59

那麼，你不能，對嗎？

結果是n*(n-1)/2元素，不管那些元素，只是在此列表中（用零說的）需要O(n^2)時間，因爲n*(n-1)/2 = O(n^2)列表...

來源

2012-02-26 12:35:33

如果我可以找到一種方法來避免內部循環，這會使它至少在理論上更快嗎？我試圖用單循環（while循環）出來，事實上，這需要更長的時間。我會發布代碼。 – 2012-02-26 15:24:07

順便提一下，運行時間複雜性並不是最壞情況下由算法和輸入的實際步驟定義的，而不是輸出？ – 2012-02-26 15:42:19

居然......不！無論你有多少內循環，都沒關係;重要的是迭代次數。即使你用單循環編寫它，這個循環也必須有n *（n-1）/ 2次迭代，所以複雜度相同。 – 2012-02-26 21:08:43

從數字列表生成所有唯一對，n選擇2

回答

相關問題