算法分析與設(shè)計(jì)2-算法分析技術(shù).ppt

1、算法分析技術(shù),第三部分,1、算法復(fù)雜性： 它是度量算法計(jì)算難度的一種尺度，反映了算法消耗的 資源情況。 算法需要資源越多，其復(fù)雜性就越高；反之， 算法需要資源越少，其復(fù)雜性就越小。,時(shí)間復(fù)雜性（Time Complexity）： 如果問(wèn)題的規(guī)模為n，解決這一問(wèn)題的某算法在算法的 輸入為I時(shí)所需的時(shí)間為T(n,I)，T(n，I)稱為算法的時(shí)間復(fù)雜性。,3.1 算法復(fù)雜性分析,空間復(fù)雜性（Space Complexity）： 如果問(wèn)題的規(guī)模為n，解決這一問(wèn)題的某算法在算法的 輸入為I時(shí)所需的空間為S(n,I)，S(n,I)稱為算法的空間復(fù)雜性。,算法分析（Algorithm Analysis）:分

2、析算法復(fù)雜性的過(guò)程；,算法的最好時(shí)間復(fù)雜性： Tmin(n)=Min T(n,I)=T(n,I*) IDn Dn是規(guī)模為n的合法輸入的集合，I*是使算法的時(shí)間達(dá)到 最小的一個(gè)輸入；,算法的復(fù)雜性除了與問(wèn)題的規(guī)模有關(guān)外，在規(guī)模一定 的情況下，輸入的分布也會(huì)影響算法的復(fù)雜性。從而就有 了最好、最壞、平均復(fù)雜性。,3.1 算法復(fù)雜性分析,算法的最壞時(shí)間復(fù)雜性： Tmax(n)=Max T(n,I)=T(n,I#) IDn Dn是規(guī)模為n的合法輸入的集合，I#是使算法的時(shí)間達(dá)到 最大的一個(gè)輸入；,算法的平均時(shí)間復(fù)雜性： Tavg(n)= P(I) T(n,I) IDn Dn是規(guī)模為n的合法輸入的集合,

3、p(I)是輸入I出現(xiàn)的概率。,3.1 算法復(fù)雜性分析,對(duì)算法空間復(fù)雜性可以同樣定義。,實(shí)踐證明，可操作性最好且最有實(shí)際價(jià)值的是最壞復(fù)雜性！,注： 輸入規(guī)模的概念和具體問(wèn)題有關(guān)，對(duì)有些問(wèn)題來(lái)說(shuō)，最自然的度量標(biāo)準(zhǔn)是輸入中的元素個(gè)數(shù)（例如，排序）；對(duì)另一些問(wèn)題其規(guī)模的最佳度量是輸入數(shù)在二進(jìn)制表示下的位數(shù)（例如整數(shù)相乘）；還有的問(wèn)題需要用兩個(gè)數(shù)表示輸入規(guī)模（例如圖的頂點(diǎn)數(shù)和邊數(shù)）。,3.1 算法復(fù)雜性分析,對(duì)于一個(gè)算法而言，在不同的執(zhí)行時(shí)間內(nèi)，它占用的內(nèi)存空間量不一定相等，也就是說(shuō)，占用空間量y是時(shí)間x的函數(shù)，即y=f(x)。,定義：時(shí)空積分= 其中t是算法的運(yùn)行時(shí)間。,時(shí)空積可以綜合評(píng)價(jià)算法的時(shí)間、

4、空間性能。,例如：一個(gè)算法的執(zhí)行時(shí)間為 30秒，前10秒算法占用60個(gè)字 節(jié)，第2個(gè)10秒占用70個(gè)字節(jié)， 最后10秒占用80個(gè)字節(jié)，則： 時(shí)空積如圖。 60*10+70*10+80*10=2100(字節(jié)秒),2、問(wèn)題的時(shí)間（空間）復(fù)雜性： 假設(shè)問(wèn)題有多個(gè)算法，所有算法的集合表示為，其中A是 其中的一個(gè)算法，即A ，它的時(shí)間（空間）復(fù)雜性表示為 TA(n),問(wèn)題的時(shí)間（空間）復(fù)雜性定義為：Min( TA(n) )。 A 即最優(yōu)算法的時(shí)間（空間）復(fù)雜性為該問(wèn)題的時(shí)間復(fù)雜性。,3.1 算法復(fù)雜性分析,3.1 算法復(fù)雜性分析,最初，我們希望精確計(jì)算出算法的復(fù)雜性（用多少時(shí)間、占多少空間）。但是，很難

5、（可比性差），也沒(méi)有必要！,精確測(cè)算出算法的性能指標(biāo)是很難的，因?yàn)椋?（1）把兩個(gè)或多個(gè)算法都寫出程序代碼須花費(fèi)很大的時(shí)間和精力； （2）可能會(huì)因?yàn)槌绦驅(qū)懙摹昂谩倍鴽](méi)有體現(xiàn)出算法的真正質(zhì)量，特別是程序員對(duì)算法有偏見時(shí)； （3）測(cè)試環(huán)境和測(cè)試數(shù)據(jù)的選擇很難對(duì)各個(gè)算法公正； （4）你覺得好的算法也不一定達(dá)到要求，要重復(fù)設(shè)計(jì)算法、寫代碼、測(cè)試。,3.1 算法復(fù)雜性分析,但是，值得注意的是無(wú)論是操作計(jì)數(shù)還是執(zhí)行步數(shù)都不能夠非常準(zhǔn)確地描述時(shí)間復(fù)雜性，特別是在需要比較時(shí)。例如: t1(n)=10n2+20n-100 t2(n)=1000n+500 哪個(gè)更好？,然后，我們又提出用評(píng)估的方法，抓主要矛盾和核心

6、的東西，用統(tǒng)計(jì)基本操作或步數(shù)來(lái)估計(jì)復(fù)雜性。,于是，既然我們的目的是為了比較，就應(yīng)該將注意力集中在被比較的對(duì)象之間最主要的差別。如果兩個(gè)程序執(zhí)行步數(shù)分別是3n+2和3n+20，則這兩個(gè)程序的時(shí)間復(fù)雜性不會(huì)有太大的差別，即使這兩個(gè)程序的每個(gè)執(zhí)行步操作數(shù)可能有所不同，這兩個(gè)程序的時(shí)間復(fù)雜性至多相差一個(gè)常數(shù)倍。,最后，就有了一個(gè)關(guān)注點(diǎn)， 算法性能的增長(zhǎng)率！,3.1 算法復(fù)雜性分析,算法的增長(zhǎng)率(growth rate)：是指當(dāng)輸入增長(zhǎng)時(shí)，算法代價(jià)的增長(zhǎng)速率。具體就體現(xiàn)在兩個(gè)函數(shù)的變化趨勢(shì)上。 T(n)=f(n) S(n)=g(n),線性增長(zhǎng)率(linear growth rate) 二次增長(zhǎng)率(qua

7、dratic growth rate) 指數(shù)增長(zhǎng)率(exponential growth rate),3.1 算法復(fù)雜性分析,換更快的計(jì)算機(jī)，還是換更快的算法？,從增長(zhǎng)率可以看出：算法不同，當(dāng)計(jì)算機(jī)速度提高時(shí)，你得到 的解決問(wèn)題規(guī)模的增益是不同的！,例如，當(dāng)計(jì)算機(jī)的運(yùn)行速度是提高為原來(lái)的10倍時(shí)，不同的算法在解決問(wèn)題的規(guī)模上得到的收益是有很大不同的。,注： n是原來(lái)解決問(wèn)題規(guī)模； n是現(xiàn)在解決問(wèn)題規(guī)模,3.1 算法復(fù)雜性分析,提高計(jì)算速度對(duì)不同時(shí)間復(fù)雜性函數(shù)的影響對(duì)比,3.1 算法復(fù)雜性分析,3、復(fù)雜性的漸近估計(jì) 對(duì)算法，精確計(jì)算其增長(zhǎng)率有時(shí)很難，如果能粗略比較出 哪個(gè)更快或更慢就可以了。于是

8、在增長(zhǎng)率的基礎(chǔ)上提出漸近估 計(jì)的概念。,算法的漸近復(fù)雜性（Asymptotic Algorithm Analysis） 確切說(shuō)：漸近分析是指當(dāng)輸入規(guī)模很大，或者說(shuō)大到一 定程度時(shí)對(duì)算法的研究和分析。（從微積分意義上說(shuō)是達(dá)到 極限時(shí)）。,3.1 算法復(fù)雜性分析,例如： t1(n)=10n t2(n)=2n2 n0=5時(shí) 總有： t1(n)t2(n) t1(n)=20n t2(n)=2n2 n0=10時(shí) 總有： t1(n)t2(n) 可以看出：增長(zhǎng)率的系數(shù)對(duì)增長(zhǎng)率的影響并不是很大。 （僅僅是改變了n0的值）,3.1 算法復(fù)雜性分析,當(dāng)擁有一臺(tái)更快的計(jì)算機(jī)時(shí)，它一定時(shí)間內(nèi)可以完成問(wèn)題的 規(guī)模增長(zhǎng)倍數(shù)

9、是一個(gè)定值，類似地，兩個(gè)增長(zhǎng)率不同的算法對(duì) 應(yīng)的曲線總會(huì)相交，增長(zhǎng)率的系數(shù)只是影響到相交的位置。,于是，當(dāng)估算算法的性能（時(shí)間或其他代價(jià)）時(shí)，經(jīng)常 忽略其增長(zhǎng)率的系數(shù)，這樣可簡(jiǎn)化算法分析，并使注意力集 中在最重要的一點(diǎn)，即增長(zhǎng)率。,這樣，我們?cè)诳紤]增長(zhǎng)率時(shí)就不用過(guò)多地專注于它的精確，而是專注于它的“數(shù)量級(jí)”或者“階！,“規(guī)?！焙汀盎静僮鳌倍际悄：母拍?！ “規(guī)?！币话闶侵篙斎肓康臄?shù)目。 “基本操作”完成該操作所需時(shí)間與操作數(shù)的具體 取值無(wú)關(guān) 。,最終，我們就可以在估算增長(zhǎng)率時(shí)主要專注于問(wèn)題的 “規(guī)?！焙汀盎镜牟僮鳌?。,3.1 算法復(fù)雜性分析,要注意：并不是任何情況都可以忽略常數(shù)！當(dāng)解決問(wèn)題

10、的 規(guī)模n很小時(shí)，系數(shù)就會(huì)起到舉足輕重的作用。,例如：t1(n)=10n t2(n)=n2 n=1: n=3: n=6:,再如：對(duì)10個(gè)數(shù)排序時(shí)使用適合于上萬(wàn)個(gè)數(shù)排序的算法 就不一定能夠效率高。,因此，漸近分析是對(duì)算法資源開銷的一種不精確的估算， 是一種“信封背面”估算，提供了對(duì)算法資源開銷進(jìn)行評(píng)估的 簡(jiǎn)單化模型。它有局限性。,3.2 算法復(fù)雜性分析中的漸近符號(hào),用來(lái)表示算法的漸近時(shí)間的記號(hào)是用定義在自然數(shù)N= 0,1,2上的函數(shù)來(lái)定義的。因?yàn)門(n)一般僅定義在整數(shù)的輸入規(guī)模上。,1. 記號(hào)漸近確界(上下限:lower bound and upper bound),(g(n) = f(n):

11、 存在正常數(shù)c1,c2和n0，使對(duì)所有的nn0，有0c1.g(n) f(n) c2.g(n) 即，對(duì)于任意一個(gè)函數(shù)f(n)，若存在正常數(shù)c1,c2,使當(dāng)n充分大時(shí)，f(n)能被夾在c1.g(n)和c2.g(n)中間，則f(n)屬于集合(g(n) 。,因?yàn)?g(n)是一個(gè)集合，所以可以寫成“ f(n) (g(n) ”。但是人們習(xí)慣寫成“f(n)= (g(n)”來(lái)表示相同的意思！,3.2 算法復(fù)雜性分析中的漸近符號(hào),由于時(shí)間和空間需求都是非負(fù)值，因此當(dāng)n足夠大時(shí)f(n)是非負(fù)值（漸近正函數(shù)），g(n)也必須是漸近非負(fù)的。,直觀圖如右：,3.2 算法復(fù)雜性分析中的漸近符號(hào),例1：證明 n2-3n=(

12、n2),要證明存在常數(shù)c1,c2和n0，使得對(duì)所有的nn0，有 c1n2 n2-3nc2n2 成立 用n2除以不等式得： c1 - c2 于是， c2 - 得知：c2 時(shí)對(duì)所有n 1成立 同樣可知， c1 - 在 c1 時(shí)對(duì)所有n 7成立 因此，取c1= c2= n07 有 c1n2 n2-3nc2n2 成立！,3.2 算法復(fù)雜性分析中的漸近符號(hào),反證法：假設(shè)成立，則存在常數(shù)c2和n0使得對(duì)所有的n n0有 6n3 c2n2 于是，n c2/6 由于c2是常數(shù)，所以對(duì)于任意大的n是矛盾的！ 結(jié)論得證。,例2：證明 6n3(n2),注意： （1）(g(n)中不同得函數(shù)，需要不同得常數(shù)！ （2）一

13、個(gè)漸近正函數(shù)中得低階項(xiàng)在決定漸近確界時(shí)可以被忽略，因?yàn)楫?dāng)n很大時(shí)它們就相對(duì)不重要了，最高階項(xiàng)很小的一部分就足以超越所有的低階項(xiàng)。 （3）一般可將c1取略小于最高階項(xiàng)系數(shù)值，可將c2取稍大于最高階項(xiàng)系數(shù)的值。,3.2 算法復(fù)雜性分析中的漸近符號(hào),例3：證明 若 f(n)=an2+bn+c 其中a,b和c都是常數(shù)，且a0 則 f(n)=(n2),取c1=a/4, c2=7a/4 n0=2.max(|b|/a, ) 有，對(duì)于所有的nn0 ,c1.n2an2+bn+cc2.n2 成立,證明：略！,定理：如果f(n)=amnm+ . + a1n + a0 且am0,則f(n)= (nm),大 比率定理：

14、對(duì)于函數(shù)f(n)和g(n)，如果極限 和 都存在，則f(n)= (g(n)當(dāng)且僅當(dāng)存在正的常數(shù)c1,c2，使得 . ,3.2 算法復(fù)雜性分析中的漸近符號(hào),例4 (1) f(n)=3n+2, g(n)=n,3n+2= (n),(2) f(n)=10n2+4n+2, g(n)=n2,f(n)=10n2+4n+2 = (n2),3.2 算法復(fù)雜性分析中的漸近符號(hào),(3) f(n)=6*2n+n2, g(n)=2n,f(n)=6*2n+n2=(2n),3.2 算法復(fù)雜性分析中的漸近符號(hào),2. O記號(hào) (漸近上界:upper bound) O記號(hào)定義增長(zhǎng)率的上界一般是指最小上界。 O(g(n) = f(

15、n): 存在正常數(shù)c和n0，使對(duì)所有的nn0，有 0f(n) c.g(n) 即，對(duì)于任意一個(gè)函數(shù)f(n)，若存在正常數(shù)c，使當(dāng)n充分大時(shí)，f(n)的值總在c.g(n)之下，則f(n)屬于集合O (g(n) 。,為了表示一個(gè)函數(shù)f(n)是集合O(g(n)的一個(gè)元素，記： f(n)=O(g(n),直觀圖如右：,3.2 算法復(fù)雜性分析中的漸近符號(hào),注意：,（1）根據(jù)集合知識(shí)，有(g(n)O(g(n),（2）an+b=O(n2) 是上界，但不是最小上界。,（3）有些文獻(xiàn)用O來(lái)非正式地描述漸近確界?，F(xiàn)在文獻(xiàn)中都將漸近確界和漸近上界區(qū)分開來(lái)。,（4）不要產(chǎn)生錯(cuò)誤界限。 例如：n2+100n+6，當(dāng)nc-1

16、00就有n2+100n+6cn。,3.2 算法復(fù)雜性分析中的漸近符號(hào),（5）用來(lái)作比較的函數(shù)g(n)應(yīng)該盡量接近所考慮的函數(shù)f(n). 例如：3n+2=O(n2) 是松散的界限；3n+2=O(n) 是較好的界限。同理，3n2+42n=O(n2)是錯(cuò)誤的界限。,（6） f(n)=O(g(n)不能寫成g(n)=O(f(n)，因?yàn)閮烧卟⒉坏葍r(jià)。 前面提到，這里的等號(hào)并不是通常相等的含義。按照定義，用集合符號(hào)更準(zhǔn)確些。,3.2 算法復(fù)雜性分析中的漸近符號(hào),大O比率定理：對(duì)于函數(shù)f(n)和g(n)，如果極限 存在，則f(n)=O(g(n)當(dāng)且僅當(dāng)存在正的常數(shù)c，使得 .,證明：略！,例如：因?yàn)?， 所以

17、 ； 因?yàn)?，所以 ； 因?yàn)?，所以 ；,3.2 算法復(fù)雜性分析中的漸近符號(hào),因?yàn)?，所以 ； 但是這不是一個(gè)好的上界估計(jì)，問(wèn)題出在極限值不 是正的常數(shù)。,因?yàn)?，所以 3n2+5O(n),O記號(hào)用來(lái)表示上界，它表示對(duì)任意的輸入，算法的最壞情況情況運(yùn)行時(shí)間的上界。即最壞時(shí)間復(fù)雜性。,3.2 算法復(fù)雜性分析中的漸近符號(hào),定理：如果f(n)=amnm+ . + a1n + a0 且am0,則f(n)=O(nm),證明：略！,下述不等式對(duì)于復(fù)雜性階的評(píng)估非常有幫助： 定理： 對(duì)于任意一個(gè)正實(shí)數(shù)x0和任一個(gè)實(shí)數(shù)0,下面的結(jié)論 都正確。 (1)存在某個(gè)n0使得對(duì)于任何nn0 ，有 。 (2)存在某個(gè)n0

18、使得對(duì)于任何nn0 ，有 。 (3)存在某個(gè)n0使得對(duì)于任何nn0 ，有 。 (4) 存在某個(gè)n0使得對(duì)于任何nn0 ，有 nxnx+ 。 (5)對(duì)任意實(shí)數(shù) y,存在某個(gè)n0使得對(duì)于任何nn0 ，有 nx(logn)ynx+ ,3.2 算法復(fù)雜性分析中的漸近符號(hào),例如 根據(jù)上面定理，我們很容易得出：,(logn)xn,(logn)xn,(logn)xn,3. 記號(hào)（漸近下界：lower bound) 記號(hào)定義增長(zhǎng)率的下界一般是指最大下界 (g(n) = f(n): 存在正常數(shù)c和n0，使對(duì)所有的nn0，有 0 c.g(n) f(n) 即，對(duì)于任意一個(gè)函數(shù)f(n)，若存在正常數(shù)c，使當(dāng)n充分大時(shí)

19、，f(n)的值等于或大于c.g(n)，則f(n)屬于集合(g(n) 。,3.2 算法復(fù)雜性分析中的漸近符號(hào),直觀表示如右圖：,例如,大 比率定理：對(duì)于函數(shù)f(n)和g(n)，如果極限 存在，則f(n)= (g(n) 當(dāng)且僅當(dāng)存在正的常數(shù)c，使得,證明：略！,3.2 算法復(fù)雜性分析中的漸近符號(hào),n/(3n+2)=1/3 所以 3n+2=(n),n2/(10n2+4n+2)=0.1 所以 10n2+4n+2 =(n2),2n/(6*2n+n2)=1/6 所以 6*2n+n2 =(2n),n/(6n2+2)=0 所以 6*n2+2 =(n),n3/(3n2+5)= 所以 3n2+5 (n),定理：如

20、果f(n)=amnm+ . + a1n + a0 且am0,則f(n)= (nm),證明：略！,3.2 算法復(fù)雜性分析中的漸近符號(hào),記號(hào)用來(lái)表示漸近下界，它表示對(duì)任意的輸入，算法的最好情況情況運(yùn)行時(shí)間的下界。即最好時(shí)間復(fù)雜性。,注意：由這三個(gè)符號(hào)的定義可以看出，盡管由漸近確界可以導(dǎo)出漸近上界和漸近下界，但是在實(shí)際應(yīng)用中是用漸近上界和漸近下界證明（導(dǎo)出）出漸近確界。,另外：一般情況下，我們不可能對(duì)每個(gè)復(fù)雜性函數(shù)去估計(jì)它們的漸近上界、漸近下界和漸近確界。,4. 記號(hào) O記號(hào)所提供的漸近上界可能是也可能不是漸近緊確的。 例如，2n2=O(n2)是漸進(jìn)緊確的， 2n=O(n2)就不是漸近緊確的。 使用

21、符號(hào)來(lái)表示非漸近緊確的上界。即： f(n)= (g(n)=對(duì)任意正常數(shù)c，存在常數(shù)n00，使得所有的nn0，有0f(n)c.g(n) ,3.2 算法復(fù)雜性分析中的漸近符號(hào),O和定義類似。主要區(qū)別是： f(n)=O(g(n)，界0f(n)c.g(n) 對(duì)某個(gè)常數(shù)c0成立； f(n)= (g(n)，界0f(n)c.g(n) 對(duì)所有常數(shù)c0成立；,也就是說(shuō)：在表示中，當(dāng)n時(shí)，函數(shù)f(n)相對(duì)于g(n)來(lái)說(shuō)就不重要了。即,5. 記號(hào) 記號(hào)與記號(hào)的關(guān)系就象記號(hào)和O記號(hào)的關(guān)系一樣。 f(n)= (g(n)=f(n):對(duì)任意正常數(shù)c0，存在常數(shù)n00，使得所有的nn0，有0 c.g(n) f(n) ,3.2

22、 算法復(fù)雜性分析中的漸近符號(hào),和定義類似。主要區(qū)別是： f(n)=(g(n)，界0 c.g(n) 0成立； f(n)=(g(n)，界0 c.g(n) 0成立；,也就是說(shuō)：在表示中，當(dāng)n時(shí)，函數(shù)g(n)相對(duì)于f(n)來(lái)說(shuō)就不重要了。即,一些常見的求和函數(shù)式的漸近表示：,3.2 算法復(fù)雜性分析中的漸近符號(hào),其中， 符號(hào)代表 中的任意一個(gè) 。,3.2 算法復(fù)雜性分析中的漸近符號(hào),實(shí)數(shù)的許多關(guān)系屬性也一樣適合漸近比較：,3.2 算法復(fù)雜性分析中的漸近符號(hào),（1）傳遞性：,f(n)=(g(n)和g(n)= (h(n) 則f(n)= (h(n) f(n)=(g(n)和g(n)= (h(n) 則f(n)=

23、(h(n) f(n)=(g(n)和g(n)= (h(n) 則f(n)= (h(n) f(n)=(g(n)和g(n)= (h(n) 則f(n)= (h(n) f(n)=(g(n)和g(n)= (h(n) 則f(n)= (h(n),（2）自反性：,f(n)=(f(n) f(n)=(f(n) f(n)=(f(n),實(shí)數(shù)的許多關(guān)系屬性也一樣適合漸近比較：,3.2 算法復(fù)雜性分析中的漸近符號(hào),（3）對(duì)稱性：,f(n)=(g(n) 當(dāng)且僅當(dāng) g(n)= (f(n),（4）轉(zhuǎn)置對(duì)稱性：,f(n)= (g(n) 當(dāng)且僅當(dāng) g(n)=(f(n) f(n)=(f(n) 當(dāng)且僅當(dāng) g(n)=(f(n),為了好理解，

24、可以將兩個(gè)函數(shù)f和g的漸近比較與兩個(gè)實(shí)數(shù)的比較類比來(lái)看：,3.2 算法復(fù)雜性分析中的漸近符號(hào),f(n)= (g(n) 類似于 a b f(n)= (g(n) 類似于 a b f(n)= (g(n) 類似于 a = b f(n)= (g(n) 類似于 a b,注意：實(shí)數(shù)集上的“三分性”不適合漸近記號(hào),對(duì)于兩個(gè)實(shí)數(shù)a和b，下列三種情況恰有一種成立： ab (這個(gè)性質(zhì)稱為“三分性”) 但是，并不是所有函數(shù)都是漸近可比較的。即，對(duì)兩個(gè)函數(shù)f(n)和g(n)，可能f(n)= (g(n)和f(n)= (g(n)都不成立，當(dāng)然f(n)= (g(n)也不成立。例如： f(n)=n , g(n)=n1+sinn

25、,3.2 算法復(fù)雜性分析中的漸近符號(hào),有時(shí)算法需要由多個(gè)函數(shù)經(jīng)過(guò)加、乘運(yùn)算組合起來(lái)的復(fù)雜函數(shù)來(lái)表示其復(fù)雜性。對(duì)復(fù)雜函數(shù)的漸近表示有下列規(guī)則：,I1 I2 I3 I4 I5 I6,3.2 算法復(fù)雜性分析中的漸近符號(hào),加法規(guī)則 針對(duì)并列程序段 T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m),乘法規(guī)則 針對(duì)嵌套程序段 T (n, m) = T1 (n) * T2 (m) = O(f (n)*g (m),3.2 算法復(fù)雜性分析中的漸近符號(hào),void exam ( float x , int m, int n ) float sum ; for ( int

26、 i = 0; i m; i+ ) sumi = 0.0; for ( int j = 0; j n; j+ ) sumi += xij; for ( i = 0; i m; i+ ) cout i “ : ” sum i endl; ,兩個(gè)并列循環(huán)的例子,漸進(jìn)時(shí)間復(fù)雜度為 O(max (m*n, m),3.2 算法復(fù)雜性分析中的漸近符號(hào),template void dataList : Sort ( ) int i = 1; int exchange = 1; while ( i ArraySize ,兩個(gè)嵌套循環(huán)的例子,3.2 算法復(fù)雜性分析中的漸近符號(hào),template void dat

27、aList: BExchange(int i, int ,3.2 算法復(fù)雜性分析中的漸近符號(hào),漸進(jìn)時(shí)間復(fù)雜度 O(f (n)*g (n) = O(n2),Sort n-1趟,BExchange ( ) n-i次比較,關(guān)于漸近表示一些有用的補(bǔ)充說(shuō)明：,1 方程式中的漸近符號(hào) 當(dāng)漸近符號(hào)只出現(xiàn)在等式的右邊，例如 n=O(n2)，等號(hào)即表示集合的成員關(guān)系，即 n O(n2)。,但是，當(dāng)漸近符號(hào)出現(xiàn)在一個(gè)公式中時(shí)，我們將其解釋為某些匿名函數(shù)。例如 ，2n2+3n+1=2n2+(n)意即2n2+3n+1=2n2+f(n)，其中f(n) 是屬于某個(gè)集合(n)的函數(shù)。此處f(n)=3n+1確實(shí)在(n)中。,

28、漸近表示的這種用法可以略去方程式中無(wú)關(guān)緊要的細(xì)節(jié)，例如，T(n)=2T(n/2)+ (n)。 如果我們對(duì)T(n)的漸近行為感興趣，就沒(méi)有必要寫出低階的項(xiàng)，它們都包含在由(n)表示的函數(shù)中。,3.2 算法復(fù)雜性分析中的漸近符號(hào),有時(shí)漸近符號(hào)出現(xiàn)在等式的左邊，例如 2n2 (n) (n2) 這時(shí)根據(jù)以下規(guī)則來(lái)解釋方程：無(wú)論等號(hào)左邊的匿名函數(shù)如阿選擇，總有辦法選取等號(hào)右面的匿名函數(shù)使等式成立。 針對(duì)例子，我們知道，對(duì)任意函數(shù)f(n) (n) ,存在函數(shù)g(n) (n2) ,使對(duì)所有的n，2n2+f(n)= g(n) ,換言之，方程右邊提供了較左邊更少的細(xì)節(jié)。,一組這樣的關(guān)系可以鏈起來(lái)，例如: 2n2

29、+3n+1=2n2+ (n) = (n2) 于是，我們可以這么來(lái)解釋：第一個(gè)方程式說(shuō)明存在函數(shù)f(n) (n) 使對(duì)所有n有2n2+3n+1=2n2+ f(n) 。第二個(gè)方程說(shuō)明對(duì)任意函數(shù)g(n) (n) ,存在函數(shù)h(n) (n2) ,對(duì)所有n有2n2+g(n)=h(n) ,這也就意味著2n2+3n+1= (n2) 。,3.2 算法復(fù)雜性分析中的漸近符號(hào),2一些標(biāo)準(zhǔn)記號(hào)和通用函數(shù),（1）上取整(Floors)下取整(Ceilings) 對(duì)于任意實(shí)數(shù)x，小于或等于x的最大整數(shù)表示為x ，大于或等于x的最小整數(shù)表示為 x 。對(duì)于所有實(shí)數(shù)x， x-10， n/a/b = n/ab n/a/b =

30、n/ab a/b (a+(b-1)/b a/b (a-(b-1)/b 下取整函數(shù)f(x)= x是單調(diào)遞增的， 上取整函數(shù)f(x)= x 也是單調(diào)遞增的。,3.2 算法復(fù)雜性分析中的漸近符號(hào),（2）取模運(yùn)算 (Modular arithmetic) 對(duì)于任意整數(shù)a和任意正整數(shù)n，a mod n的值即是a/n的余數(shù)： a mod n = a- a/n n,同余：如果(a mod n) = (b mod n)，稱在模n時(shí)，a等于b，即a和b被n除時(shí)余數(shù)相同。記作 ab(mod n) ab(mod n)當(dāng)且僅當(dāng)n是b-a的一個(gè)約數(shù)。,3.2 算法復(fù)雜性分析中的漸近符號(hào),（3）多項(xiàng)式 給定一個(gè)正整數(shù)，的

31、次多項(xiàng)式是具有如下形式的函數(shù)p(n)： d p(n)=aini i=0 其中常數(shù)a0,a1,ad是多項(xiàng)式的系數(shù)，且ad0。,一個(gè)多項(xiàng)式是漸近正的，當(dāng)且僅當(dāng)ad0。 對(duì)于一個(gè)d次的漸近正多項(xiàng)式p(n)，有p(n)= (nd)。 對(duì)于任意實(shí)常數(shù)a0，函數(shù)na單調(diào)遞增； 對(duì)于任意實(shí)常數(shù)a0， 函數(shù)na單調(diào)遞減； 對(duì)某個(gè)常數(shù)k有f(n)=O(nk)，則稱函數(shù)f(n)有多項(xiàng)式界；,3.2 算法復(fù)雜性分析中的漸近符號(hào),（4）指數(shù)式 對(duì)于任意實(shí)數(shù)a0，m和n，有下列恒等式： a0=1 ，a1=a ， a-1=1/a (am)n=amn， (am)n=(an)m， aman=am+n,3.2 算法復(fù)雜性分析中

32、的漸近符號(hào),對(duì)任意n和a1，函數(shù)an關(guān)于n單調(diào)遞增； 對(duì)任意實(shí)數(shù)a和b，且a1，有： =0 因此，根據(jù)前面的定義可知 nbo(an) 即 任何底大于1的指數(shù)函數(shù)比任何多項(xiàng)式函數(shù)增長(zhǎng)的更快！,用e表示2.71828，即自然對(duì)數(shù)函數(shù)的底，對(duì)任意實(shí)數(shù)x x2 x3 xi ex =1+x+ + + = 2! 3! i=0 i!,對(duì)任意實(shí)數(shù)x，有不等式： ex 1+x 只有x=0時(shí)等號(hào)才成立； 當(dāng) |x|1時(shí)，有近似式： 1+xex1+x+x2 當(dāng)x0時(shí)，用1+x來(lái)近似ex的效果相當(dāng)好： ex=1+x+ (x2) 對(duì)任意的x，有： x lim ( 1+ )n =ex n n,3.2 算法復(fù)雜性分析中的漸

33、近符號(hào),（5）對(duì)數(shù) 一般約定： lgn=log2n lnn=logen lgkn=(lgn)k lglgn=lg(lgn) lgn+k=(lgn)+k,3.2 算法復(fù)雜性分析中的漸近符號(hào),函數(shù)來(lái)logbn在常數(shù)b大于1時(shí)，關(guān)于n0嚴(yán)格遞增。,改變一個(gè)對(duì)數(shù)的底只是把對(duì)數(shù)的值改變了一個(gè)常數(shù)倍，所以當(dāng)不在意這些常數(shù)因子時(shí)常采用“l(fā)gn”記號(hào)，就象O記號(hào)一樣。一般認(rèn)為對(duì)數(shù)的底取2最為自然，因?yàn)楹芏嗨惴ê蛿?shù)據(jù)結(jié)構(gòu)都涉及到對(duì)問(wèn)題的二分。,當(dāng)|x|-1時(shí)，還有以下不等式成立： x ln(1+x) x 只有x=0時(shí)等號(hào)才成立 1+x,3.2 算法復(fù)雜性分析中的漸近符號(hào),如果對(duì)常數(shù)k，函數(shù)f(n)=O(lgkn

34、) ，則稱f(n)是多項(xiàng)對(duì)數(shù)有界的。 由前面我們已知： nb lim 0 n an 于是用lg n 代替n ，用2a代替a，于是可以將多項(xiàng)式增長(zhǎng)率和多項(xiàng)對(duì)數(shù)增長(zhǎng)率聯(lián)系起來(lái)： lgbn lgbn lim lim =0 n (2a)lgn n na 因此對(duì)于任意常數(shù)a0，有： lgbno(na) 即任意正的多項(xiàng)式函數(shù)都比多項(xiàng)對(duì)數(shù)函數(shù)增長(zhǎng)得快！,3.2 算法復(fù)雜性分析中的漸近符號(hào),（6）階乘 階乘函數(shù)的一個(gè)弱上界是 n! nn 。,斯特林近似公式： n 1 n!= ()n (1+ () e n 給出了一個(gè)更緊確的上界和下界。其中e是自然對(duì)數(shù)的底。 有用結(jié)論： n!=o(nn) n!=(2n) lg(

35、n!)= (nlgn),3.2 算法復(fù)雜性分析中的漸近符號(hào),3.2 算法復(fù)雜性分析中的漸近符號(hào),1、算法分析的一般步驟： （1）計(jì)算基本操作、基本存儲(chǔ)占用的數(shù)量； （2）求出累計(jì)和函數(shù)T(n),S(n)； （3）給出漸近表示。,3.3 算法復(fù)雜性分析的內(nèi)涵,2、算法復(fù)雜性的實(shí)質(zhì)： 問(wèn)題規(guī)模變化與資源消耗的關(guān)系！,漸進(jìn)復(fù)雜性分析的重要性 很多人認(rèn)為：隨著計(jì)算機(jī)技術(shù)的發(fā)展，低效算法無(wú)所謂了！ 其實(shí)不然，“壞”算法終究是“壞”算法，不因?yàn)橛?jì)算機(jī)速度的 提高它就成了“好”算法！,對(duì)低效算法（一般是超線性的）來(lái)說(shuō)，計(jì)算機(jī)本身性能的提高不能帶來(lái)求解問(wèn)題規(guī)模的增益。即：計(jì)算機(jī)速度提高了，我們希望在原來(lái)的時(shí)間

36、內(nèi)解決問(wèn)題的規(guī)模變大，或希望解決原來(lái)相同規(guī)模的問(wèn)題時(shí)時(shí)間相應(yīng)的變短，但結(jié)果可能不是你想象的那樣好，這與你使用的算法有關(guān)！,3.3 算法復(fù)雜性分析的內(nèi)涵,注意： （1）“復(fù)雜性漸進(jìn)階比較低的算法比復(fù)雜性的漸進(jìn)階比較高的算法有效”，只是在問(wèn)題規(guī)模充分大時(shí)才成立。 （2） 當(dāng)兩個(gè)算法的復(fù)雜性漸進(jìn)階相同時(shí)，必須進(jìn)一步考察T（n）的常數(shù)因子,3.4 一般算法的時(shí)間復(fù)雜性分析,1、賦值、讀、寫等一般看作基本操作； 2、劃分三種控制結(jié)構(gòu)； 3、對(duì)各種控制結(jié)構(gòu)，有 （1）順序操作序列，可以累加或取最大值； （2）分支的條件判斷一般看作基本操作，分支結(jié)構(gòu)的時(shí)間 定義為條件成立和不成立時(shí)的和； （3）循環(huán)結(jié)構(gòu)的時(shí)

37、間為循環(huán)體的時(shí)間乘循環(huán)次數(shù)； 4、函數(shù)調(diào)用時(shí)要考慮函數(shù)的執(zhí)行時(shí)間。 給出基本操作的計(jì)數(shù)(或步數(shù)統(tǒng)計(jì)) 漸近表示：最好給出,各個(gè)符號(hào)的表示!,3.5 遞歸算法的復(fù)雜性分析,遞歸算法是比較特殊的一類算法，其分析過(guò)程一般有下面幾步： 1、分析遞歸算法，寫出遞歸方程 2、求解遞歸方程； 3、給出遞歸方程解的漸近表示； 其中，求解遞歸方程式是關(guān)鍵，也是比較難的一步！,3.5 遞歸算法的復(fù)雜性分析,遞歸方程的求解,當(dāng)一個(gè)算法包含對(duì)自身的遞歸調(diào)用時(shí)，其運(yùn)行時(shí)間通常用 遞歸式來(lái)表示。遞歸式是一組等式或不等式，它所描述的函數(shù) 是用在更小的輸入下該函數(shù)的值來(lái)定義的。,例如，數(shù)據(jù)結(jié)構(gòu)中介紹的“歸并”分類算法的最壞運(yùn)

38、行時(shí)間 可以用下面的遞歸式來(lái)描述： (1) n=1 T(n)= 2T(n/2)+ (n) n1 其解為T(n)= (nlgn) 求解遞歸方程，是數(shù)學(xué)里的一類問(wèn)題，有些是比較難的， 我們介紹三種在算法分析中常用的方法。,3.5 遞歸算法的復(fù)雜性分析,一代換法,“代換法”這一名稱源于當(dāng)歸納假設(shè)用較小值時(shí)，用所猜測(cè) 的值代替函數(shù)的解。它可用來(lái)確定一個(gè)遞歸式的上界或下界。 這種方法很有效，但是只能用于解的形式很容易猜的情形。,1用代換法解遞歸式需要兩個(gè)步驟： 1）猜測(cè)解的形式 2）用數(shù)學(xué)歸納法找出使解真正有效的常數(shù),例如，有下面的遞歸式： T(n)=2T( n/2 )+n，我們可以用代換法來(lái)確定它的一

39、個(gè)上界。,首先，從前面的一些結(jié)論我們可以猜測(cè)，T(n) cnlgn，其中c0是某個(gè)常數(shù)。,3.5 遞歸算法的復(fù)雜性分析,一代換法,然后，用歸納法來(lái)確定常數(shù)c。先假設(shè)這個(gè)界對(duì) n/2 成立，即 T(n/2 ) c n/2 lg( n/2 )，代入原式，于是有： T(n)=2T( n/2 )+n 2 (c n/2 lg( n/2 )+n cnlg(n/2)+n =cnlgn cnlg2+n =cnlgn-cn+n cnlgn (只要c1) 可以歸納證明，c 2時(shí)，對(duì)于n 2 都成立（根據(jù)漸近表示要求，n0可以把不符合的邊界區(qū)分開來(lái)） 于是有T(n) cnlgn，結(jié)論獲證！,3.5 遞歸算法的復(fù)雜性

40、分析,一代換法,2需要注意的問(wèn)題,1）做一個(gè)好的猜測(cè) 不存在通用的方法來(lái)猜測(cè)遞歸式正確的解，需要經(jīng)驗(yàn)和創(chuàng)新。但是有些探試法可以幫助做出好的猜測(cè)。 如果某個(gè)遞歸式與以前見過(guò)的類似，則可以猜測(cè)該遞歸式有類似的解。例如，對(duì) T(n)=2T( n/2 +17)+n 我們可以猜測(cè)其解為 T(n)=O(nlgn)。 另一方法是，先證明遞歸式的輕松的上下界，然后再縮小不確定性區(qū)間。,3.5 遞歸算法的復(fù)雜性分析,一代換法,2需要注意的問(wèn)題,2）一些細(xì)微問(wèn)題 有時(shí)，我們或許能夠猜出遞歸式的漸近界，但卻會(huì)在歸納證明時(shí)出現(xiàn)問(wèn)題。通常，問(wèn)題出在歸納假設(shè)不夠強(qiáng)，無(wú)法證明其準(zhǔn)確的界。遇到這種情況時(shí)，可以去掉一個(gè)低階項(xiàng)來(lái)

41、修正所猜的界，以使證明順利進(jìn)行。,例如有下面的遞歸式： T(n)=T( n/2 )+T( n/2 )+1 根據(jù)經(jīng)驗(yàn)我們猜測(cè)：T(n)=O(n)，即要證明對(duì)適當(dāng)選擇的c，有 T(n) cn。,3.5 遞歸算法的復(fù)雜性分析,一代換法,用所猜測(cè)的界對(duì)遞歸式做替換，于是得到： T(n)= T( n/2 )+T( n/2 )+1 c n/2 + c n/2 +1 = c (n/2 + c n/2 )+1 = cn+1 由此看出，無(wú)論c為何值，都得不出 T(n) cn的結(jié)論。,于是，人們或許就猜測(cè)一個(gè)更大的界，例如T(n)=O(n2)，這的確是它的一個(gè)上界，但它不是最小的上界。而事實(shí)上，我們猜的很正確。為

42、了歸納證明，我們需要做一個(gè)更強(qiáng)的歸納假設(shè)。從直觀上看，我們猜的與上面歸納推的結(jié)論只差一個(gè)常數(shù)“1”，即一個(gè)看似無(wú)關(guān)的低階項(xiàng)，但是就是這個(gè)低階項(xiàng)卻使得數(shù)學(xué)歸納法無(wú)法證明出期望的結(jié)果。,3.5 遞歸算法的復(fù)雜性分析,一代換法,現(xiàn)在，我們用降階來(lái)修正猜測(cè)的界，即從所作的猜測(cè)中減去一個(gè)低階的項(xiàng)，即有 T(n) cn-b，b0是常數(shù)。然后我們?cè)偃w納證明。,將假設(shè)代入，有： T(n)= T( n/2 )+T( n/2 )+1 (c n/2 -b + c n/2 -b)+1 = cn-2b+1 cn-b (只要b1) 同時(shí)c要取得足夠大，以便能夠處理邊界條件。,好象我們感覺從猜測(cè)中減去一項(xiàng)與直覺不符合，為

43、什么不增加一項(xiàng)來(lái)解決問(wèn)題呢？這關(guān)鍵是由數(shù)學(xué)歸納法本身決定的：通過(guò)更小的值做更強(qiáng)的假設(shè)，就可以證明對(duì)某個(gè)給定值的更強(qiáng)的結(jié)論。,3.5 遞歸算法的復(fù)雜性分析,一代換法,2需要注意的問(wèn)題,3）避免陷阱 在運(yùn)用漸近符號(hào)時(shí)很容易出錯(cuò)，記?。何覀円?dú)w納證明的是準(zhǔn)確的形式。例如：由假設(shè)T(n) cn , 然后： T(n)=2T( n/2 )+n 2(c n/2 )+n cn+n =O(n) 這個(gè)結(jié)論是錯(cuò)誤的，因?yàn)槲覀兿Ｍ瞥龅氖菧?zhǔn)確的形式：T(n) cn,3.5 遞歸算法的復(fù)雜性分析,一代換法,2需要注意的問(wèn)題,4）改變變量 有時(shí)，對(duì)于一個(gè)陌生，看似復(fù)雜的遞歸式做一些簡(jiǎn)單的變換，就會(huì)變成我們較為熟悉的形式，

44、從而可以根據(jù)經(jīng)驗(yàn)做出好的猜測(cè)。,例如，有遞歸式 T(n)=2T( )+lgn，我們可以按下面的方法進(jìn)行變換： 1）不考慮整數(shù)截取 2）設(shè)m=lgn, 于是 n=2m ， =2m/2 于是有： T(2m)=2T(2m/2)+m 再假設(shè) S(m)=T(2m)，于是就有：S(m)=2S(m/2)+m 根據(jù)前面的猜測(cè)我們知道，S(m)=O(mlgm)。再將S(m)代回去得：T(n)=T(2m)=S(m)=O(mlgm)=O(lgn lglgn),3.5 遞歸算法的復(fù)雜性分析,二遞歸樹法,雖然代換法給遞歸式的解的正確性提供了一種簡(jiǎn)單的證明方法，但是有時(shí)候很難得到一個(gè)好的猜測(cè)。而畫出遞歸樹是一種得到好的猜

45、測(cè)的直接方法。,遞歸樹的構(gòu)造方法是：首先將遞歸式轉(zhuǎn)化為一棵等價(jià)樹，該樹的樹根結(jié)點(diǎn)是頂層遞歸的代價(jià)，根的子樹是根據(jù)遞歸式推出的更小的遞歸式。即首先T(n)擴(kuò)展為一棵等價(jià)的樹，然后再依次下去，繼續(xù)擴(kuò)展遞歸式的各個(gè)結(jié)點(diǎn)，即將其分解成由遞歸式所決定的各個(gè)組成部分，直到問(wèn)題規(guī)模降到了最小。,在遞歸樹中，每個(gè)結(jié)點(diǎn)都代表遞歸函數(shù)調(diào)用集合中一個(gè)子問(wèn)題的代價(jià)。將樹中每一層的代價(jià)相加得到一個(gè)每層代價(jià)的集合，再將每層的代價(jià)相加得到遞歸式所有層次的總代價(jià)。,3.5 遞歸算法的復(fù)雜性分析,二遞歸樹法,例如，對(duì)于遞歸式 T(n)2T(n/2)+cn，遞歸樹構(gòu)造為：,T(n),cn,T(n/2),T(n/2),cn,cn/

46、2,cn/2,T(n/4),T(n/4),T(n/4),T(n/4),3.5 遞歸算法的復(fù)雜性分析,cn,cn/2,cn/2,cn/4,cn/4,cn/4,cn/4,c c c c c c c c c c c c c c c,n,lgn,cn,cn,cn,cn,3.5 遞歸算法的復(fù)雜性分析,二遞歸樹法,遞歸樹最適合來(lái)產(chǎn)生好的猜測(cè)，然后用代換法加以驗(yàn)證。但是，在用遞歸樹產(chǎn)生好的猜測(cè)時(shí)，由于后面還要對(duì)猜測(cè)進(jìn)行歸納證明，所以產(chǎn)生遞歸樹時(shí)可以是一個(gè)大致的粗略的，即不一定是非常嚴(yán)格的全部生成出來(lái)。,如果生成遞歸樹時(shí)非常仔細(xì)完整，并且將代價(jià)都加了起來(lái)，那么就可以直接用遞歸樹來(lái)作為遞歸式解的證明，這也就是我

47、們經(jīng)常用的展開法求解遞歸式的解。,請(qǐng)你自己試著畫出遞歸式 T(n)=3T(n/4)+cn2 的遞歸樹，并猜測(cè)其解。,3.5 遞歸算法的復(fù)雜性分析,三主方法,主方法(master method)給出求解如下形式的遞歸式的“食譜”方法。 T(n)=aT(n/b)+f(n) 其中 a1和b1是常數(shù)，f(n)是一個(gè)漸近正的函數(shù)。,主方法要求只要記憶三種情況，就可以很容易地確定一些遞歸式的解，而且不用紙和筆！,上面的遞歸式描述了將規(guī)模為n的問(wèn)題劃分為a個(gè)子問(wèn)題的算法的運(yùn)行時(shí)間，每個(gè)子問(wèn)題的規(guī)模為n/b，a和b是正常數(shù)，a個(gè)問(wèn)題被遞歸地解決，其花時(shí)間為T(n/b)。劃分原問(wèn)題與合并答案的代價(jià)用函數(shù)f(n)

48、來(lái)描述。,3.5 遞歸算法的復(fù)雜性分析,三主方法,3.5 遞歸算法的復(fù)雜性分析,三主方法,主定理的應(yīng)用：,再例如： ，這里 ， ， 由于 ， =(1) 所以由公式()有 。,3.6 復(fù)雜性分析舉例,Insertion_sort(A) for j2 to length(A) do key Aj /將Aj插入到有序序列A1.j-1 i j-1 while(i0)and(Aikey) do Ai+1 Ai i i-1 Ai+1 key ,例1：分析下面插入分類的時(shí)間復(fù)雜性,假設(shè)tj為對(duì)每個(gè)j值時(shí)while循環(huán)的運(yùn)行次數(shù)，于是有各個(gè)代碼行的 執(zhí)行次數(shù)如上。又假設(shè)n=length(A),Cost times c1 n c2 n-1 c3=0 n-1 c4 n-1 c5 tj c6 (tj-1) c7 (tj-1) c8 n-1,于是， T(n)=c1n+c2(n-1)+c4(n-1)+c5tj+c6 (tj-1)+c7(tj-1)+c8(n-1),3.6 復(fù)雜性分析舉例,另外，在輸入規(guī)模一定時(shí)，不同的輸入樣本實(shí)例會(huì)影響算法的運(yùn)行時(shí)間。 例如，當(dāng)輸入序列已經(jīng)排好序時(shí)，對(duì)于每一個(gè)j，都有tj=1， ，出現(xiàn)最好情況，于是有: T(n)=c1n+c2(n-1)+c4(n-1)+c5(n-1)+c8(n-1)