綠的家具

[Alg] 94交大資工12題There are two collections A= {a1,…,ak}and B={b1,…bk}of k<=nDistinct integers selected from{1,…n} Design an O(k logk) algoto find all the numbers that occur in both A and B[Hint: Using sorting]algo 1. 將A排序，使用高等排序法，quick , merge, or heap sort. T(klogk) 2. 將B排序，方法同上。  T(klogk) 3. for(i=1 to k) 在B中，搜尋ai的值，使用binary search. k*T(logk) O(n) = T(klogk)+T(klogk)+k*T(logk) = O(klogk) 我也覺得這樣就可以了 sorting完以後 A和B A1和B1開始讀，小的就讀下一個  遇到Ai和Bj是一樣的 就把這一對丟出來 讀完A和B O(n) 加上sorting的 O(nlogn) 還是O(nlogn) .msgcontent .wsharing ul li { text-indent: 0; } 分享 Facebook Plurk YAHOO! .