1、簡(jiǎn)單不相交集的合并算法 本節(jié)的假定前提：1、為算法書寫方便起見，設(shè)任一集合 都是1,2,n的子集；2、任意兩個(gè)被合并的集合都是不相交的；3、集合上的運(yùn)算 只有Union和Find。Union(I,J,K):把名為I與J的集合進(jìn)行合并，合并后的集合名為K。初始共有n個(gè)單元素集，故Union最多可執(zhí)行n-1次即O(n)。Find(a):給出a所在的集合名(算法中大多用數(shù)字表示集合名)。此類問題中Find指令的執(zhí)行通常也有 O(n)次，故一般 討論執(zhí)行O(n)條Union和Find指令所需要的時(shí)間。可以用來表示集合的數(shù)據(jù)結(jié)構(gòu)很多，用什么樣的算法和結(jié)構(gòu)才能使得完成上述任務(wù)的時(shí)間最少？Union(I,J

2、,K)算法中的數(shù)組說明：為加快處理速度，每個(gè)集合給予一個(gè)內(nèi)部名和一個(gè)外部名。內(nèi)部名與外部名1 1對(duì)應(yīng)。例如：外部名123集合1,3,5,72,4,86內(nèi)部名231算法涉及6個(gè)數(shù)組，4個(gè)與集合相關(guān)，2個(gè)與元素相關(guān)。數(shù)組元素 External-NameS:內(nèi)部名為S（數(shù)字）的集合所對(duì)應(yīng)的外部名。數(shù)組元素 Internal-NameL:外部名為L(zhǎng)（數(shù)字）的集合所對(duì)應(yīng)的內(nèi)部名。數(shù)組元素Ri:給出元素i所屬集合的內(nèi)部名。（Find指令可在O（1）時(shí)間內(nèi)完成）Nexti:給出與元素i同在一個(gè)集合中的下一個(gè)元素，內(nèi)容為0時(shí)，表示無下一元素（即元素i是該集合的最后一個(gè)元素）。數(shù)組元素ListS:給出內(nèi)部名為S

3、的集合中的第一個(gè)元素。數(shù)組元素SizeS:給出內(nèi)部名為S的集合中的元素個(gè)數(shù)。AInternal-NameI;/*將集合外部名I,J轉(zhuǎn)為內(nèi)部名A和B*/B -Internal-NameJ;wlg assume SizeA - SizeB/*A為小集合，B為大集合*/otherwise interchange roles of A and B inELEMENT - ListA;/*找出集合A的第一個(gè)元素*/while ELEMENT * 0 do/*不斷把 A 中*/*元素所在的集合名改為B,直到全部改完為止*/RELEMENT B;/* 改名*/LAST ELEMENT;/*記下當(dāng)前元素 */

4、ELEMENT - NextELEMENT;/*更新當(dāng)前元素，準(zhǔn)備執(zhí)行下一輪*/*循環(huán)結(jié)束時(shí)，*/*LAST中記錄了原集合A中的最后一個(gè)元素*/NextLAST - ListB;/*置該元素的下一個(gè)元素為原B中的第一個(gè)元素，*/*從而實(shí)現(xiàn)A和B的合并*/ListB - ListA;/*置合并后的首元素為原 A中的首元素*/SizeB -SizeA + SizeB;/*置集合大小為A、B兩集合的規(guī)模之和*/Internal-NameK B;/*建立新集合的內(nèi)部名與外部名的對(duì)應(yīng)關(guān)系*/External-NameB K Union算法除6-9行以外，其余均為常數(shù)時(shí)間。在最壞情況下，即當(dāng) A和B的規(guī)模

5、均為n/2時(shí)，6-9行要執(zhí)行n/2次，以完成其中一個(gè)集合的元素所屬集改 名。即最壞情況下執(zhí)行1次Union需要的時(shí)間為0 (n)。在最壞情況下，執(zhí)行n-1次Union需要的時(shí)間是否為0 (n2)?對(duì)6-9行進(jìn)行總體分析,即考慮執(zhí)行n-1次Union需要的總時(shí)間 TOC o 1-5 h z 每次總是小集合中的元素所屬集合改名，每執(zhí)行一次Union ,被改名元素所在集合的規(guī)模至少擴(kuò)大一倍。考慮任意一個(gè)元素i能夠被改名的次數(shù)：初始時(shí)i所在集合只有一個(gè)元素，改名一次以后，i所在集合的元素至少有2個(gè)，再改名一次以后，i所在集合的元素至少有 4個(gè)， 故當(dāng)i改名k次后，i所在集合的元素至少有 2k個(gè)，而2k

6、 * n是必須滿足的，故有 k * Log 2n ,即任一元素i最多被改名Log 2n次(i=1,2，,n), 故n個(gè)元素的改名總次數(shù)不會(huì)超過n*Log 2n ,即在n-1次Union中，6-9行執(zhí)行改名的次數(shù)不超過 0 (n logn)。在最壞情況下，改名總次數(shù)是可能達(dá)到。(n logn)的：E.g.設(shè)n=2k,先把單元素集兩兩合并為雙元素集；再把雙元素集兩兩合并為 4元素集；最后把兩個(gè)n/2元素集合并為一個(gè)總的 n元素集。在上述每一輪，需要改名的元素恰好為n/2個(gè)，共執(zhí)行k=Log 2n輪，故改名的總次數(shù)為 1/2*nLog 2n。 說明：若沒有內(nèi)部名，則每次合并時(shí)兩個(gè)集合中的所有元素均要改名(改為K),這樣，在n-1次Union中改名的次數(shù)就會(huì)大大超過上述方式O另外，如果合并時(shí)不進(jìn)行外部命名，即用Union（I,J）的形式，則不需要另外再建立內(nèi)部名，合并時(shí)仍然是小集合中的元素改名。總的開銷比上述算法少一些，（減