




版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 21夏日絕句(教學(xué)設(shè)計(jì))2024-2025學(xué)年統(tǒng)編版語(yǔ)文四年級(jí)上冊(cè)
- 讓孩子在幼兒園中感受到家的溫馨計(jì)劃
- 2025年調(diào)崗合同模板
- 技術(shù)轉(zhuǎn)讓技術(shù)秘密協(xié)議(2025年版)
- 六年級(jí)下冊(cè)數(shù)學(xué)教案-總復(fù)習(xí) 統(tǒng)計(jì)中的策略|北師大版
- 落地玻璃窗安全教育
- 2025年助懸劑合作協(xié)議書(shū)
- 2025年廢棄資源和廢舊材料回收加工品項(xiàng)目發(fā)展計(jì)劃
- 店面出租合同協(xié)議書(shū)
- 膀胱癌病人的化療護(hù)理
- 重點(diǎn)流域水環(huán)境綜合治理中央預(yù)算內(nèi)項(xiàng)目申報(bào)指南
- 民用無(wú)人機(jī)操控員執(zhí)照(CAAC)考試復(fù)習(xí)重點(diǎn)題庫(kù)500題(含答案)
- 家族合伙企業(yè)合同協(xié)議書(shū)
- 工業(yè)機(jī)器人編程語(yǔ)言:URScript(UniversalRobots):UR機(jī)器人安全編程與碰撞檢測(cè)
- 5.1 實(shí)數(shù)指數(shù)冪-中職數(shù)學(xué)教學(xué)設(shè)計(jì)(高教版2021基礎(chǔ)模塊 下冊(cè))
- 大學(xué)生心理安全教育(大學(xué)生安全教育課件)
- 藝考培訓(xùn)合作合同協(xié)議書(shū)2024年
- 人教版英語(yǔ)中考一輪教材梳理復(fù)習(xí)教案(七-九年)(共1份打包)
- 巖土工程領(lǐng)域的前沿技術(shù)與未來(lái)發(fā)展
- 國(guó)家開(kāi)放大學(xué)電大《現(xiàn)代漢語(yǔ)》形考任務(wù)參考答案
- 2024年天津市北辰城市資源開(kāi)發(fā)利用有限公司招聘筆試沖刺題(帶答案解析)
評(píng)論
0/150
提交評(píng)論