生成不相交的位指針對的列表

Question

Give是一組元素，其中每個元素都有一個分數和一個位指針。我想創建一個所有對的列表，其中這兩個元素的位指針是不相交的。

我天真的僞代碼的做法是：

result = new_list_of_pairs() 

foreach(i = 0; i < set.size; i++) 
    foreach(j = i+1; j < set.size; j++) 
     if(set[i].bitpointer & set[j].bitpointer == 0) 
     result.add(set[i], set[j]); 
    } 
} 

是否有更好的算法解決了這個問題，因爲這個算法的運行時間是O（n^2）？

Answer 1

在最壞的情況下不可能獲得更好的時間複雜度，因爲可能有O(n^2)這樣的對。