中科大算法導(dǎo)論第一二次和第四次作業(yè)答案PPT學(xué)習(xí)教案_第1頁(yè)
中科大算法導(dǎo)論第一二次和第四次作業(yè)答案PPT學(xué)習(xí)教案_第2頁(yè)
中科大算法導(dǎo)論第一二次和第四次作業(yè)答案PPT學(xué)習(xí)教案_第3頁(yè)
中科大算法導(dǎo)論第一二次和第四次作業(yè)答案PPT學(xué)習(xí)教案_第4頁(yè)
中科大算法導(dǎo)論第一二次和第四次作業(yè)答案PPT學(xué)習(xí)教案_第5頁(yè)
已閱讀5頁(yè),還剩13頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、會(huì)計(jì)學(xué)1中科大算法導(dǎo)論第一二次和第四次作業(yè)中科大算法導(dǎo)論第一二次和第四次作業(yè)答案答案2.3-2改寫(xiě)MERGE過(guò)程,使之不使用哨兵元素,而是在一旦數(shù)組L或R中的所有元素都被復(fù)制回?cái)?shù)組A后,就立即停止,再將另一個(gè)數(shù)組中余下的元素復(fù)制回?cái)?shù)組A中。MERGE(A,p,q,r)1.n1q-p+12.n2 r-q3.create arrays L1.n1 and R1.n24.for i 1 to n15. do Li Ap+i-16.for j 1 to n27. do Rj Aq+j8.i 19.j 110.k p11.while(i=n1) and (j=n2)12. do if Li=Rj13.

2、do Ak=Li14. i+15. else do Ak=Rj16. j+17. k+18.while(i=n1)19. do Ak+=Li+20.while(j=n2)21. do Ak+=Rj+第1頁(yè)/共18頁(yè))lg()!(lg,!)2(2nnnnnnnn兩邊取對(duì)數(shù)可知:證明:由于第2頁(yè)/共18頁(yè)第3頁(yè)/共18頁(yè)).lg(2/(2)(nnOnnTnT的解為證明)lg()(),lg()()1c(lg) 1c ( -lg)2/lg()2/lg(2/2)2/(2)(2/lgT(n), 01lg1lg)(1)(T1nnnTnnOnTncnnncnnncnnnncnnTnTnncncncnnTnn下

3、面證所以,時(shí)當(dāng)成立對(duì)假設(shè)是唯一的邊界條件,時(shí),證明:假設(shè)當(dāng)?shù)?頁(yè)/共18頁(yè)).lg()()lg()(,lg)(23/1c0 1) 1lg() 1lg()21 (, 3/1c) 1lg()21 () 1lg()1 (1lg1)1(lg, 2)11lg()1lg(0) 1lg()1 (1lg0lg21lg) 1(lg21lg) 1(21lg) 1(21lg212)2/lg(2/2)2/(2)()2/lg()2/()2/(TnnnTnnnTncnnTnnnccncnccncnccncncnncnnnnnnncncncnncnncnnnncncnnnncnnncnnncnnncnnTnTnncn所以時(shí)

4、,有,取則取則是遞增函數(shù),取則成立。設(shè)第5頁(yè)/共18頁(yè)1)()2/()2/(1n)1 ()(nnnTnTnT如果如果第6頁(yè)/共18頁(yè)ncnnTccnnncnnncncnncnncncncnnTnnnnnncncnnncncnnncnncncncnnncnncncnncnnncnncnnncnncnnncnncnnTnTnTnncnTncnnTnnOlg)(0)1(4),1(4,012)1lg(3)1(4(4)12)1(lg(2lg)(212)1lg(22lg)(1)11lg(1n)11lg(lg)1lg()()12(2)1lg(2)lg)1(lg(2lg)()12(2)lg(2)1lg(2)1

5、lg(2)(2lg2)lg(221)1lg(21)()2lg(2)21lg(21)()2lg(2)21lg(21)()2/lg()2/()2/lg()2/()()2/()2/()()2/lg()2/()2/(lg)()lg(即有取,有取則有,有是遞增函數(shù),取則成立設(shè),即要證證明:先證第7頁(yè)/共18頁(yè)ncnnTccnnncnncncnnncncncnnTnnnnnnncncnnncncnnncncnncnncncnnncnncncnncnncnncncnncnnncnncnnncnncnnTnTnTnncnTncnnTnnlg)(0)2) 1 () 1 (21, 0) 1lg(1, 3n)2)

6、1 ()1lg(1(2lg)() 1lg(2) 13(2lg)(1)11lg(, 2)11lg(lg) 1lg()() 1lg(2) 12(2)lg) 1(lg(2lg0)() 1lg(2) 12(2) 1lg(2lg2lg)() 1lg(2) 1lg(2) 12(2lg2)(2lg21) 1lg(212lg2lg2)()21lg(21)2lg(2)()2/lg()2/()2/lg()2/()()2/()2/()()2/lg()2/()2/(lg)(),lg(,有取有取有是遞增函數(shù),取則成立,設(shè)即要證再證第8頁(yè)/共18頁(yè)ncnnTncnnnncnncccnnncnnnccnnncncnncnn

7、cnnncnncnncncnnnncnncncnnnncnncnnncnncnnncnncnnTnTnTnncnTncnnTnnOlg)(lg)()2lg(2)21lg(210)1(4),1(4,02)1lg(23)1(4(4)2)1lg(2(421)()1lg(2)(212)1lg(2)11lg(21)11lg(1n)11lg(0)(212)1lg(2)11lg(20lg)()2lg(2)21lg(21lg)()2lg(2)21lg(21)()2lg(2)21lg(21)()2/lg()2/()2/lg()2/()()2/()2/()()2/lg()2/()2/(lg)()lg(即有取,有取

8、,有是遞增函數(shù),取則成立設(shè),即要證證明方法二:先證第9頁(yè)/共18頁(yè)ncnnTncnnnncnncccnnncnnccnncnncnncnncnnnncnncnncncnnnncnncncnnnncnncnnncnncnnncnncnnTnTnTnncnTncnnTnnlg)(lg)()21lg(21)2lg(20)2) 1 () 1 (21, 0) 1lg(1, 3n)2) 1 ()1lg(1(2213) 1lg(2)()(212) 1lg(2)11lg(21)11lg(, 2)11lg(0)(212) 1lg(2)11lg(20lg)()21lg(21)2lg(2lg)()21lg(21)2lg(2)()21lg(21)2lg(2)()2/lg()2/()2/lg()2/()()2/()2/()()2/lg()2/()2/(lg)(),lg(即,有取有取有是遞增函數(shù),取則成立,設(shè)即要證再證第10頁(yè)/共18頁(yè)2/)(rpq第11頁(yè)/共18頁(yè)int Partition(int A, int p, int r) int x = Ar,i=p-1; int flag = 1; for (int j = p;j=Ai&flag0)/x=Ai時(shí),flag大于0和小于0的數(shù)量約

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論