下載本文檔
版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第1、2章練習(xí)1.講義習(xí)題一:第1(執(zhí)行步改為關(guān)鍵操作數(shù))、第2、3、6、7題習(xí)題一1答：執(zhí)行步4pmn+3pm+2m+1;關(guān)鍵操作2n*m*p2方法一答：2n-2次方法二答：2n-2次31）證明：任給c，n>c,則10n2>cn。不存在c使10n2<=cn,證畢。2)證明：任給c，當(dāng)n>2c時(shí)，logn>c，從而n2logn>=cn2,同上。6答：logn，n2/3，20n，4n2，3n，n!7答：1)6+n2)3)任意n2.講義習(xí)題二：第6題。答：c、e是割點(diǎn)。每點(diǎn)的DFN、L值：A1,1、B2,1、C3,1、D4,4、E5,1、F6,5、G7,5。最大連通分支CD、EFG、ABCE。3.考慮下述選擇排序算法：輸入：n個(gè)不等的整數(shù)的數(shù)組A[1..n]輸出：按遞增次序排序的AFori:=1ton-1Forj:=i+1tonIfA[j]<A[i]thenA[i]A[j]問：(1)最壞情況下做多少次比較運(yùn)算？答1+2+..+n-1=n(n-1)/2(2)最壞情況下做多少次交換運(yùn)算？在什么輸入時(shí)發(fā)生？答：當(dāng)輸入的n個(gè)數(shù)彼此不等且按遞降次序排列時(shí)，比較次數(shù)n(n-1)/2，每次比較都交換，交換次數(shù)n(n-1)/2。4.考慮下面的每對(duì)函數(shù)f(n)和g(n),比較他們的階。(1)f(n)=(n2-n)/2,g(n)=6n(2)f(n)=n+2,g(n)=n2(3)f(n)=n+nlogn,g(n)=n(4)f(n)=log(n!),g(n)=答：(1)g(n)=O(f(n))(2)f(n)=O(g(n)(3)f(n)=O(g(n)(4)f(n)=O(g(n)5.在表中填入true或false.答案：f(n)g(n)f(n)=O(g(n)f(n)=(g(n))f(n)=(g(n))12n3+3n100n2+2n+100FTF250n+logn10n+loglognTTT350nlogn10nloglognFTF4lognLog2nTFF5n!5nFTF6.用迭代法求解下列遞推方程：(1)(2),n=2k答：(1)T(n)=T(n-1)+n-1=T(n-2)+n-2+n-1=…=T(1)+1+2+…+n-1=n(n-1)/2=O(n2)(2)T(n)=2T(n/2)+n-1=2(2T(n/4)+n/2-1)+n-1=4T(n/4)+n-2+n-1=4(2T(n/23)+n/4-1)+n-2+n-1=23T(n/23)+n-4+n-2+n-1=…=2kT(n/2k)+n-2k-1+n-2k-2+…+n-1
溫馨提示
- 1. 本站所有資源如無(wú)特殊說明，都需要本地電腦安裝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ù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
- 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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年代理費(fèi)用協(xié)議范本
- 2025年銷售人員任職協(xié)議書：互聯(lián)網(wǎng)銷售團(tuán)隊(duì)建設(shè)協(xié)議2篇
- 2025年度風(fēng)力發(fā)電場(chǎng)建設(shè)與運(yùn)營(yíng)合同范本4篇
- 二零二五年藝術(shù)品鑒定兼職人員保密責(zé)任書3篇
- 基于2025年度房產(chǎn)政策的商品房銷售合同
- 2025年度跨境電子商務(wù)稅收風(fēng)險(xiǎn)擔(dān)保協(xié)議4篇
- 二零二五年度直播主播與影視作品合作合同
- 2025年度供應(yīng)鏈金融貨物沖抵貨款風(fēng)險(xiǎn)控制協(xié)議
- 二零二五年度門面房房屋租賃押金合同
- 二零二五年度汽車抵押抵貨款保理合同
- 寒潮雨雪應(yīng)急預(yù)案范文（2篇）
- 垃圾車駕駛員聘用合同
- 變壓器搬遷施工方案
- 單位轉(zhuǎn)賬個(gè)人合同模板
- 八年級(jí)語(yǔ)文下冊(cè) 成語(yǔ)故事 第十五課 諱疾忌醫(yī) 第六課時(shí) 口語(yǔ)交際教案 新教版（漢語(yǔ)）
- 2024年1月高考適應(yīng)性測(cè)試“九省聯(lián)考”數(shù)學(xué) 試題（學(xué)生版+解析版）
- EPC項(xiàng)目采購(gòu)階段質(zhì)量保證措施
- T-NAHIEM 101-2023 急診科建設(shè)與設(shè)備配置標(biāo)準(zhǔn)
- 四川2024年專業(yè)技術(shù)人員公需科目“數(shù)字經(jīng)濟(jì)與驅(qū)動(dòng)發(fā)展”參考答案（通用版）
- 煤炭裝卸服務(wù)合同
- 廣東省佛山市順德區(qū)2023學(xué)年中考一模物理試題（含答案解析）
評(píng)論
0/150
提交評(píng)論