算法設(shè)計(jì)第六次課

1、1第三章第三章 環(huán)上選舉算法環(huán)上選舉算法汪汪 煬煬2上節(jié)中的兩個(gè)算法在同步環(huán)上最壞的上節(jié)中的兩個(gè)算法在同步環(huán)上最壞的msg復(fù)雜度為復(fù)雜度為O(n)，但，但兩算法的兩算法的缺陷缺陷為：為： 它們用一種非同尋常的方式使用它們用一種非同尋常的方式使用id，即，即id決定決定msg延遲多延遲多長(zhǎng)；長(zhǎng)； 在每個(gè)容許的執(zhí)行中，執(zhí)行輪數(shù)依賴于在每個(gè)容許的執(zhí)行中，執(zhí)行輪數(shù)依賴于id，而，而id相對(duì)于相對(duì)于n而而言可能是巨大的。言可能是巨大的。(更主要的更主要的)本節(jié)將說(shuō)明：本節(jié)將說(shuō)明： 這些性質(zhì)對(duì)于有效的這些性質(zhì)對(duì)于有效的msgmsg算法而言是固有的；算法而言是固有的； 若一個(gè)算法中的標(biāo)識(shí)符僅用于比較，則它需

2、要若一個(gè)算法中的標(biāo)識(shí)符僅用于比較，則它需要(nlgn)個(gè)個(gè)msgs； 若一個(gè)算法中，限制輪數(shù)的上界，但獨(dú)立于若一個(gè)算法中，限制輪數(shù)的上界，但獨(dú)立于id，則它的，則它的msg復(fù)雜度亦為復(fù)雜度亦為(nlgn)。3.4.2 有限制算法的下界有限制算法的下界(nlgn)(nlgn)時(shí)間復(fù)雜度會(huì)表現(xiàn)很差時(shí)間復(fù)雜度會(huì)表現(xiàn)很差3n 同步的下界不可能從異步的下界導(dǎo)出同步的下界不可能從異步的下界導(dǎo)出因?yàn)樯瞎?jié)中的算法表明：同步模型中的附加假定是因?yàn)樯瞎?jié)中的算法表明：同步模型中的附加假定是必不可少的。必不可少的。n 同步的下界對(duì)于非均勻和均勻算法均成立，但異步的同步的下界對(duì)于非均勻和均勻算法均成立，但異步的下界只對(duì)

3、均勻算法成立。下界只對(duì)均勻算法成立。n 但是從同步導(dǎo)出的異步結(jié)果是正確的，并且提供了一但是從同步導(dǎo)出的異步結(jié)果是正確的，并且提供了一個(gè)非均勻算法的異步下界。個(gè)非均勻算法的異步下界。3.4.2 有限制算法的下界有限制算法的下界(nlgn)(nlgn)異步通信模型中領(lǐng)導(dǎo)者選舉問(wèn)題異步通信模型中領(lǐng)導(dǎo)者選舉問(wèn)題所需的消息數(shù)下界為所需的消息數(shù)下界為(nlgn)且且算法不依賴于比較的或者限時(shí)的算法不依賴于比較的或者限時(shí)的41.基于比較的算法的概念和定義基于比較的算法的概念和定義 為了得到下界，假定所有處理器在為了得到下界，假定所有處理器在同一輪開(kāi)始執(zhí)行同一輪開(kāi)始執(zhí)行 一個(gè)環(huán)是由結(jié)點(diǎn)表按順時(shí)針?lè)较蛑付ǖ?，結(jié)

4、點(diǎn)表開(kāi)始于最一個(gè)環(huán)是由結(jié)點(diǎn)表按順時(shí)針?lè)较蛑付ǖ?，結(jié)點(diǎn)表開(kāi)始于最小標(biāo)識(shí)符。小標(biāo)識(shí)符。 在同步模型里，算法的容許執(zhí)行完全由初始配置定義，這在同步模型里，算法的容許執(zhí)行完全由初始配置定義，這是因?yàn)槭且驗(yàn)閙sg延遲及節(jié)點(diǎn)步驟的相對(duì)次序均無(wú)選擇的可能。延遲及節(jié)點(diǎn)步驟的相對(duì)次序均無(wú)選擇的可能。 系統(tǒng)的初始配置完全由環(huán)決定，即由節(jié)點(diǎn)標(biāo)識(shí)符列表按上系統(tǒng)的初始配置完全由環(huán)決定，即由節(jié)點(diǎn)標(biāo)識(shí)符列表按上述規(guī)則來(lái)決定。當(dāng)算法的選擇可以從上下文判斷清楚時(shí)，述規(guī)則來(lái)決定。當(dāng)算法的選擇可以從上下文判斷清楚時(shí)，則將由環(huán)則將由環(huán)R確定的容許執(zhí)行表示為確定的容許執(zhí)行表示為exec(R).n 匹配：匹配：若環(huán)若環(huán)R1上的結(jié)點(diǎn)上的結(jié)

5、點(diǎn)pi和和R2上的上的pj在各自的環(huán)里具有相同在各自的環(huán)里具有相同的位置，則稱的位置，則稱pi和和pj是匹配的，即：匹配的結(jié)點(diǎn)在各自環(huán)上是匹配的，即：匹配的結(jié)點(diǎn)在各自環(huán)上距其最小距其最小id的結(jié)點(diǎn)的距離相同。的結(jié)點(diǎn)的距離相同。3.4.2 有限制算法的下界有限制算法的下界(nlgn)(nlgn)5n 基于比較的算法基于比較的算法 直觀上，若一個(gè)算法在兩個(gè)相對(duì)次序相同的環(huán)上直觀上，若一個(gè)算法在兩個(gè)相對(duì)次序相同的環(huán)上具有相具有相同的行為同的行為，則該算法是基于比較的，形式定義：，則該算法是基于比較的，形式定義：1）序相同）序相同 兩個(gè)環(huán)兩個(gè)環(huán)x0, x1, xn-1和和y0, y1,yn-1是是(次

6、次)序等價(jià)的，若序等價(jià)的，若對(duì)每個(gè)對(duì)每個(gè)i和和j，xixj, 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)yi0)，則它在前，則它在前n輪里就沒(méi)有任何輪里就沒(méi)有任何msg存在。存在。但同樣認(rèn)為前但同樣認(rèn)為前n輪對(duì)每個(gè)結(jié)點(diǎn)是有用的。輪對(duì)每個(gè)結(jié)點(diǎn)是有用的。 因此，若某一輪在任何次序等價(jià)的環(huán)上均無(wú)因此，若某一輪在任何次序等價(jià)的環(huán)上均無(wú)msg發(fā)送，發(fā)送，則該輪是則該輪是無(wú)用無(wú)用的，而有用的輪被稱為是的，而有用的輪被稱為是主動(dòng)的主動(dòng)的(active)。3.4.2 有限制算法的下界有限制算法的下界(nlgn)(nlgn)10 Def 3.3 在一個(gè)環(huán)在一個(gè)環(huán)R上的一個(gè)執(zhí)行里，某輪上的一個(gè)執(zhí)行里，某輪r稱為是稱為是active的，若的

7、，若該執(zhí)行的第該執(zhí)行的第r輪里，某一個(gè)結(jié)點(diǎn)發(fā)送一個(gè)輪里，某一個(gè)結(jié)點(diǎn)發(fā)送一個(gè)msg。當(dāng)。當(dāng)R是從上下文是從上下文清楚時(shí)，用清楚時(shí)，用rk表示第表示第k個(gè)個(gè)active輪。輪。 Note： 一旦環(huán)一旦環(huán)R確定，整個(gè)容許執(zhí)行就確定確定，整個(gè)容許執(zhí)行就確定(因?yàn)橄到y(tǒng)同步因?yàn)橄到y(tǒng)同步) 由于一個(gè)基于比較的算法在等價(jià)環(huán)上的行為相似，因此：由于一個(gè)基于比較的算法在等價(jià)環(huán)上的行為相似，因此： 對(duì)于序等價(jià)的環(huán)對(duì)于序等價(jià)的環(huán)R1和和R2，一輪在，一輪在exec(R1)里是主動(dòng)的當(dāng)且僅里是主動(dòng)的當(dāng)且僅當(dāng)它在當(dāng)它在exec(R2)里也是主動(dòng)的。里也是主動(dòng)的。 因?yàn)橄⒅械男畔⒃谝驗(yàn)橄⒅械男畔⒃趉個(gè)輪里只能在環(huán)上通過(guò)

8、個(gè)輪里只能在環(huán)上通過(guò)k個(gè)結(jié)點(diǎn)，所以個(gè)結(jié)點(diǎn)，所以一個(gè)結(jié)點(diǎn)在一個(gè)結(jié)點(diǎn)在k輪之后的狀態(tài)只依賴于它的輪之后的狀態(tài)只依賴于它的k-鄰居。鄰居。 然而一個(gè)更強(qiáng)的性質(zhì)是：一個(gè)結(jié)點(diǎn)在第然而一個(gè)更強(qiáng)的性質(zhì)是：一個(gè)結(jié)點(diǎn)在第k個(gè)主動(dòng)輪之后的狀個(gè)主動(dòng)輪之后的狀態(tài)只依賴于它的態(tài)只依賴于它的k-鄰居。這實(shí)際上告訴我們：信息只有在主動(dòng)輪鄰居。這實(shí)際上告訴我們：信息只有在主動(dòng)輪里才能獲得。這一點(diǎn)在下面的引理中給出形式證明。里才能獲得。這一點(diǎn)在下面的引理中給出形式證明。3.4.2 有限制算法的下界有限制算法的下界(nlgn)(nlgn)113.4.2 有限制算法的下界有限制算法的下界(nlgn) Note：該引理無(wú)需結(jié)點(diǎn)匹配：

9、該引理無(wú)需結(jié)點(diǎn)匹配(否則立即從定義否則立即從定義3.2中可中可得結(jié)論得結(jié)論)，但要求它們的鄰居是相同的，但要求它們的鄰居是相同的(identical)。該引理。該引理要求假設(shè)兩個(gè)環(huán)是次序等價(jià)的，原因是要確?？紤]中的兩要求假設(shè)兩個(gè)環(huán)是次序等價(jià)的，原因是要確?？紤]中的兩個(gè)執(zhí)行有相同的主動(dòng)輪集合，因此個(gè)執(zhí)行有相同的主動(dòng)輪集合，因此rk是良定義的。是良定義的。 Lemma3.16 設(shè)設(shè)R1和和R2是次序等價(jià)的兩個(gè)環(huán)，設(shè)是次序等價(jià)的兩個(gè)環(huán)，設(shè)Pi和和Pj分分別是別是R1和和R2上具有相同上具有相同k-鄰居的兩個(gè)節(jié)點(diǎn)，那么在鄰居的兩個(gè)節(jié)點(diǎn)，那么在exec(R1)的第的第1至第至第rk輪里輪里Pi所經(jīng)歷的轉(zhuǎn)

10、換序列和在所經(jīng)歷的轉(zhuǎn)換序列和在exec(R2)的第的第1至第至第rk輪里輪里Pj所經(jīng)歷的轉(zhuǎn)換序列相同。所經(jīng)歷的轉(zhuǎn)換序列相同。/該引理蘊(yùn)含：在該引理蘊(yùn)含：在k個(gè)主動(dòng)輪結(jié)束時(shí)，個(gè)主動(dòng)輪結(jié)束時(shí)，Pi和和Pj的狀態(tài)相同的狀態(tài)相同 Pf：非形式地，該證明說(shuō)明在非形式地，該證明說(shuō)明在k個(gè)主動(dòng)輪之后，一個(gè)結(jié)點(diǎn)個(gè)主動(dòng)輪之后，一個(gè)結(jié)點(diǎn)可能只知道距離自己至多為可能只知道距離自己至多為k的那些結(jié)點(diǎn)。形式證明對(duì)的那些結(jié)點(diǎn)。形式證明對(duì)k進(jìn)進(jìn)行歸納。行歸納。123.4.2 有限制算法的下界有限制算法的下界(nlgn) 歸納基礎(chǔ)歸納基礎(chǔ)：k=0，因?yàn)閮蓚€(gè)具有相同，因?yàn)閮蓚€(gè)具有相同0-鄰居的結(jié)點(diǎn)有同樣的鄰居的結(jié)點(diǎn)有同樣的id

11、，故它們的狀態(tài)相同；，故它們的狀態(tài)相同； 歸納假設(shè)歸納假設(shè)：假定每?jī)蓚€(gè)具有相同：假定每?jī)蓚€(gè)具有相同(k-1)-鄰居的結(jié)點(diǎn)在鄰居的結(jié)點(diǎn)在(k-1)個(gè)個(gè)主動(dòng)輪之后有相同的狀態(tài)；主動(dòng)輪之后有相同的狀態(tài)； 歸納步驟歸納步驟：因?yàn)椋阂驗(yàn)镻i和和Pj有相同的有相同的k-鄰居，故它們亦有相同的鄰居，故它們亦有相同的(k-1)-鄰居。因此由歸納假設(shè)知，鄰居。因此由歸納假設(shè)知，Pi和和Pj在第在第(k-1)個(gè)主動(dòng)輪個(gè)主動(dòng)輪之后處在相同的狀態(tài)。又因之后處在相同的狀態(tài)。又因Pi和和Pj各自的鄰居有同樣的各自的鄰居有同樣的(k-1)-鄰居，故由歸納假設(shè)知，它們各自的鄰居在第鄰居，故由歸納假設(shè)知，它們各自的鄰居在第(k

12、-1)個(gè)主個(gè)主動(dòng)輪之后也處在相同的狀態(tài)。動(dòng)輪之后也處在相同的狀態(tài)。兩個(gè)主動(dòng)輪之間可能有非主動(dòng)輪。兩個(gè)主動(dòng)輪之間可能有非主動(dòng)輪。因?yàn)樵诘谝驗(yàn)樵诘?k-1)主動(dòng)輪和第主動(dòng)輪和第k主動(dòng)輪之間的輪主動(dòng)輪之間的輪(若有的話若有的話)里，里，沒(méi)有結(jié)點(diǎn)接收任何沒(méi)有結(jié)點(diǎn)接收任何msg，故，故Pi和和Pj及各自的鄰居均處在相同及各自的鄰居均處在相同的狀態(tài)的狀態(tài)(Note: Pi在非主動(dòng)輪里可能改變它的狀態(tài)，但因?yàn)樵诜侵鲃?dòng)輪里可能改變它的狀態(tài)，但因?yàn)镻j有同樣的轉(zhuǎn)換函數(shù)，故它有同樣的狀態(tài)轉(zhuǎn)換有同樣的轉(zhuǎn)換函數(shù)，故它有同樣的狀態(tài)轉(zhuǎn)換)。133.4.2 有限制算法的下界有限制算法的下界(nlgn)在第在第k個(gè)主動(dòng)輪里：

13、個(gè)主動(dòng)輪里： i)若若Pi和和Pj均不接收均不接收msg，則它們?cè)谠撦喗Y(jié)束時(shí)有相同的狀態(tài)；，則它們?cè)谠撦喗Y(jié)束時(shí)有相同的狀態(tài)； ii)因?yàn)橐驗(yàn)镻i 和和Pj的鄰居狀態(tài)相同，若的鄰居狀態(tài)相同，若Pi接收右接收右(左左)鄰的一個(gè)鄰的一個(gè)msg，則則Pj也接收右也接收右(左左)鄰?fù)瑯拥泥復(fù)瑯拥膍sg。因此，在第。因此，在第k個(gè)主動(dòng)輪結(jié)束個(gè)主動(dòng)輪結(jié)束之后，之后，Pi和和Pj均處于相同的狀態(tài)。均處于相同的狀態(tài)。下一引理將上述論斷從具有相同下一引理將上述論斷從具有相同k-鄰居的結(jié)點(diǎn)擴(kuò)展至具有鄰居的結(jié)點(diǎn)擴(kuò)展至具有次序等價(jià)的次序等價(jià)的k-鄰居的結(jié)點(diǎn)。這依賴于事實(shí)：鄰居的結(jié)點(diǎn)。這依賴于事實(shí)：A是基于比較的。是基于

14、比較的。更進(jìn)一步要求環(huán)更進(jìn)一步要求環(huán)R是是有空隙有空隙的，即環(huán)的，即環(huán)R中，每?jī)蓚€(gè)中，每?jī)蓚€(gè)id之間均之間均有有n個(gè)未使用的標(biāo)識(shí)符。形式地，在大小為個(gè)未使用的標(biāo)識(shí)符。形式地，在大小為n的環(huán)上，若對(duì)于的環(huán)上，若對(duì)于每一個(gè)標(biāo)識(shí)符每一個(gè)標(biāo)識(shí)符x，標(biāo)識(shí)符，標(biāo)識(shí)符x-1到到x-n均不在環(huán)上，則該環(huán)稱為有均不在環(huán)上，則該環(huán)稱為有空隙的?？障兜摹?43.4.2 有限制算法的下界有限制算法的下界(nlgn)引理引理3.16定義在兩環(huán)上定義在兩環(huán)上(Pi和和Pj的的k-鄰居相同鄰居相同)，引理，引理3.17是定義在同一個(gè)環(huán)上是定義在同一個(gè)環(huán)上(Pi和和Pj的的k-鄰居序等價(jià)鄰居序等價(jià))Lemma3.17 設(shè)設(shè)R

15、是有空隙環(huán)，是有空隙環(huán)，Pi和和Pj是是R上具有序等價(jià)上具有序等價(jià)k-鄰居的兩個(gè)結(jié)點(diǎn)。則鄰居的兩個(gè)結(jié)點(diǎn)。則Pi和和Pj在在exec(R)的第的第1到第到第rk輪里輪里有相似的行為。有相似的行為。Pf：我們構(gòu)造滿足下述條件的另一個(gè)環(huán)我們構(gòu)造滿足下述條件的另一個(gè)環(huán)R： R中的中的Pj和和R中中Pi的有相同的的有相同的k-鄰居；鄰居； R中的標(biāo)識(shí)符唯一中的標(biāo)識(shí)符唯一 R和和R序等價(jià)，序等價(jià)，R中的中的Pj匹配于匹配于R中的中的Pj。因?yàn)橐驗(yàn)镽是有空隙環(huán)，故我們能夠構(gòu)造是有空隙環(huán)，故我們能夠構(gòu)造R。例如，對(duì)于。例如，對(duì)于k=1和和n=8有：有：153.4.2 有限制算法的下界有限制算法的下界(nlgn

16、)10302040609075100PjPiR6090759192949395PjPiR R R Pi的的1-鄰居鄰居60，90，75 Pj的的1-鄰居鄰居60，90，75 R中中id唯一唯一 R次序：次序： R次序：次序： 10,30,20,40,60,90,75,100 60,90,75,91,92,94,93,95Pj與與10距離為距離為1，Pj與與60距離為距離為1163.4.2 有限制算法的下界有限制算法的下界(nlgn)(1)R上的上的Pi和和R上的上的Pj的前的前k個(gè)主動(dòng)輪行為相似個(gè)主動(dòng)輪行為相似 因?yàn)橐驗(yàn)镽上上Pi和和R上上Pj的的k-鄰居相同鄰居相同，由引理，由引理3.16知

17、，知，Pi和和Pj在各在各自的自的exec(R)和和exec(R)的的1到到rk輪里所經(jīng)歷的轉(zhuǎn)換序列相同，輪里所經(jīng)歷的轉(zhuǎn)換序列相同，所以所以Pi和和Pj在各自的執(zhí)行在各自的執(zhí)行exec(R)和和exec(R)的的1至至rk輪里的行輪里的行為相似。為相似。 Pi(R) Pj(R)(2)R上的上的Pj和和R上的上的Pj的前的前k個(gè)主動(dòng)輪行為相似個(gè)主動(dòng)輪行為相似 因?yàn)樗惴ㄊ腔诒容^的，故在兩個(gè)序等價(jià)的環(huán)中，每對(duì)匹配的因?yàn)樗惴ㄊ腔诒容^的，故在兩個(gè)序等價(jià)的環(huán)中，每對(duì)匹配的結(jié)點(diǎn)在各自執(zhí)行中有相似的行為。而結(jié)點(diǎn)在各自執(zhí)行中有相似的行為。而R里的里的Pj和和R里的里的Pj是是匹配匹配的，故的，故R里的里的P

18、j在在exec(R)的的1至至rk輪里的行為相似于輪里的行為相似于R里的里的Pj在在exec(R)的第的第1至至rk輪里的行為。輪里的行為。 Pj(R) Pj(R)(3)R上兩節(jié)點(diǎn)的上兩節(jié)點(diǎn)的k-鄰居序等價(jià)，則其行為在前鄰居序等價(jià)，則其行為在前k個(gè)主動(dòng)輪里相似個(gè)主動(dòng)輪里相似 由由(1)和和(2)得：得：R里的里的Pi和和Pj在在exec(R)的的1至至rk輪里的行為相似。輪里的行為相似。Pi(R) Pj(R) 173.4.2 有限制算法的下界有限制算法的下界(nlgn)Th3.18 對(duì)于每個(gè)對(duì)于每個(gè)n8(n是是2的冪的冪)，存在一個(gè)大小為，存在一個(gè)大小為n的環(huán)的環(huán)Sn，使，使得對(duì)每個(gè)基于比較的

19、同步得對(duì)每個(gè)基于比較的同步leader選舉算法選舉算法A，在，在Sn上上A的容的容許執(zhí)行里發(fā)送許執(zhí)行里發(fā)送msg的數(shù)目為的數(shù)目為(nlgn)Pf：固定算法固定算法A。證明分。證明分2步：步： (1) 構(gòu)造構(gòu)造1個(gè)高度對(duì)稱個(gè)高度對(duì)稱(很多結(jié)點(diǎn)有很多序等價(jià)的鄰居很多結(jié)點(diǎn)有很多序等價(jià)的鄰居)的環(huán)的環(huán)Sn； (2) Sn上發(fā)送的上發(fā)送的msg總數(shù)?？倲?shù)。 （1）構(gòu)造）構(gòu)造Sn（分（分2步構(gòu)造）步構(gòu)造） 定義大小為定義大小為n的環(huán)的環(huán) ： 對(duì)對(duì)i0，n-1，設(shè)，設(shè)Pi的的id為為rev(i)，這里，這里rev(i)是是i的二進(jìn)的二進(jìn)制表示的逆序列。制表示的逆序列。 RrevnrevnRrevnR183.

20、4.2 有限制算法的下界有限制算法的下界(nlgn)例如，當(dāng)例如，當(dāng)n=8時(shí)有：時(shí)有： 若將環(huán)若將環(huán) 劃分為劃分為長(zhǎng)度為長(zhǎng)度為j(j是是2的方冪的方冪)的連續(xù)片斷，則所的連續(xù)片斷，則所有這些片斷是序等有這些片斷是序等價(jià)的價(jià)的(Ex3.9)。 片斷數(shù)片斷數(shù)：n / j.0002=0P0R8rev1002=40102=21102=60012=11012=50112=31112=7P1P2P3P4P5P6P7revnR例如，例如，4,2,6,1和和5,3,7,0序等價(jià)序等價(jià) 2,6,1,5和和3,7,0,4序等價(jià)序等價(jià)193.4.2 有限制算法的下界有限制算法的下界(nlgn) 從從 構(gòu)造構(gòu)造Sn

21、將將 上每個(gè)上每個(gè)id乘以乘以(n+1)再加上再加上n所獲得的所獲得的Sn是有空是有空隙環(huán)。但這種變化不改變片斷的序等價(jià)性。隙環(huán)。但這種變化不改變片斷的序等價(jià)性。 (2) Sn上發(fā)送的上發(fā)送的msg總數(shù)（分總數(shù)（分3步）步） 求求Sn中中序等價(jià)的鄰居集數(shù)目序等價(jià)的鄰居集數(shù)目（引理（引理3.19） 由由證明算法里證明算法里主動(dòng)輪數(shù)目下界主動(dòng)輪數(shù)目下界（引理（引理3.20） 由由求求每個(gè)主動(dòng)輪里發(fā)送每個(gè)主動(dòng)輪里發(fā)送msg數(shù)目的下界數(shù)目的下界(引理引理3.21) 由由和和的的組合即可獲得算法的組合即可獲得算法的msg復(fù)雜性下界。復(fù)雜性下界。revnRrevnR203.4.2 有限制算法的下界有限制算

22、法的下界(nlgn)Lemma3.19 對(duì)所有對(duì)所有Kn/8以及每個(gè)以及每個(gè)Sn的的k-鄰居集鄰居集N，在，在Sn中與中與N序等價(jià)的序等價(jià)的k-鄰居集的個(gè)數(shù)鄰居集的個(gè)數(shù)(包括包括N本身本身)大于大于 Pf：N由由2k+1個(gè)個(gè)id構(gòu)成，設(shè)構(gòu)成，設(shè)j是大于是大于2k+1的的2的最小方冪。將的最小方冪。將Sn劃分為劃分為n/j個(gè)連續(xù)片斷，使某一片段包含個(gè)連續(xù)片斷，使某一片段包含N。由由Sn的構(gòu)造可知，上述劃分所得的所有片段均是序等價(jià)的構(gòu)造可知，上述劃分所得的所有片段均是序等價(jià)的。因此，的。因此，至少至少有有n/j個(gè)鄰居集和個(gè)鄰居集和N是序等價(jià)的。是序等價(jià)的。設(shè)設(shè)j=2i，2i-12k+12i，j2(21)nk 2(21)nnjk213.4.2 有限制算法的下界有限制算法的下界(nlgn)Lemma3.20 在在exec(Sn)里，主動(dòng)輪的數(shù)目至少為里，主動(dòng)輪的數(shù)目至少為n/8。Pf：設(shè)主動(dòng)輪數(shù)目設(shè)主動(dòng)輪數(shù)目T8，n為為2的方冪，存在一個(gè)大小為的方冪，存在一個(gè)大小為n的的環(huán)環(huán)R，使得