




已閱讀5頁(yè),還剩30頁(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)介
計(jì)算機(jī)算法分析 習(xí)題課 第四章: 2 、 3、 5、 6、 10、 11、 23 下列情況下求解 (n)= ()2(/2) () 足夠小否則 當(dāng) g(n)=O(1)和 f(n)=O(n); g(n)=O(1)和 f(n)=O(1)。 設(shè) n=2 T(n)=T(2k)=2T(2f(2k) =2(2 T(2f(2 +f(2k) =22T(221f(2 f(2k) = =2)+2)+22)+ +20f(2k) =2kg(n)+ 2)+22)+ +20f(2k) g(n)=O(1)和 f(n)=O(n) 當(dāng) g(n)=O(1)和 f(n)=O(n)時(shí) 不妨設(shè) g(n)=a, f(n)=: T(n)=T(2k) = 22b+22b+ +20*22ka+an+(g(n)=O(1)和 f(n)=O(1) 當(dāng) g(n)=O(1)和 f(n)=O(1)時(shí), 不妨設(shè) g(n)=c, f(n)=d,則: T(n)=T(2k) = +20d =d(2=(c+d) (n) 根據(jù) 一個(gè)二分檢索的遞歸過(guò)程 。 , x, j) if (2 if x=A(j if xA(, , x, j); if xA( :; j 0 例運(yùn)行 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 361 時(shí)間復(fù)雜度 成功 : O(1),O(n),O(n) 最好,平均,最壞 失敗 : O(n),O(n),O(n) 最好,平均,最壞 于含有 明 E=I+2n 其中, E, 證明:數(shù)學(xué)歸納法 當(dāng) n=1時(shí),易知 E=2, I=0,所以 E=I+2 假設(shè) n k(k0)時(shí), E=I+2 此時(shí)新樹內(nèi)部結(jié)點(diǎn)為 滿足: k+2k( 1) 考察原樹的外部路徑長(zhǎng)度和內(nèi)部路徑長(zhǎng)度: = (h+1) ( 2) =Ik+h( 3) 綜合( 1)( 2)( 3)式: = k+h+2 = k+h+2 = +2(k+1) 故命題成立。 程 (它的最好情況時(shí)間是什么?能說(shuō)歸并分類的時(shí)間是 (? 最好情況: 對(duì)有序文件進(jìn)行排序 分析 歸并的次數(shù)不會(huì)發(fā)生變化 n)次 歸并中比較的次數(shù)會(huì)發(fā)生變化(兩個(gè)長(zhǎng) n/2序列歸并) 最壞情況 兩個(gè)序列交錯(cuò)大小 需要比較 最好情況 一個(gè)序列完全大于 /小于另一個(gè)序列 比較 n/2次 差異都是線性的,不改變復(fù)雜性的階 最好情況也是 n), 平均復(fù)雜度 n)。 寫一個(gè) “由底向上 ”的歸并分類算法,從而取消對(duì)??臻g的利用。 見數(shù)據(jù)結(jié)構(gòu) 238 算法 R, n, 1X) 初始化 i 1 合并相鄰的兩個(gè)長(zhǎng)度為 i n 2* 1 R, i, i l, i 2* X) . i i 2* 處理余留的長(zhǎng)度小于 2* IF i+ 0,要用的處理時(shí)間 ,限期 解:根據(jù) (30,20,18,6,5,3,1),對(duì)應(yīng)的期限為 (2,4,3,1,3,1,2),按照算法 )=7(2), )=7(2), J(2)=3(4); )=7(2), J(2)=4(3),J(3)=3(4); )=6(1), J(2)=7(2),J(3)=4(3),J(4)=3(4); 證明即使作業(yè)有不同的處理時(shí)間定理 里,假定作業(yè) ,要用的處理時(shí)間 ,限期 定理 個(gè)作業(yè)的集合 , = 它使得 當(dāng)且僅當(dāng) 的次序又不違反任何一個(gè)期限的情況下來(lái)處理 . 證明:顯然即使 ( 如果 J 中的作業(yè)可以按照 的次序而又不違反任何一個(gè)期限來(lái)處理,即對(duì) 次序中的任一個(gè)作業(yè) k,應(yīng)滿足 = J 就是一個(gè)可行解。下面證明如果 J 是可行解, =得 J 中的作業(yè)可以按照 列排列而又不違反任何一個(gè)期限。 J 是可行解,則必存在 =使得對(duì)任意的 有 =們?cè)O(shè) 是按照 列的作業(yè)序列。假設(shè) ,那么令 a 是使 最小下標(biāo),設(shè) rb=然 ba,在 中將 交換,因?yàn)?然 以按期完成作業(yè), 我們還要證明 間的作業(yè)也能按期完成 。因?yàn)?顯然二者之間的所有作業(yè) 有 由于 是可行解,所以 1 ,所以作業(yè) 換后,仍滿足 1 ,即所有作業(yè)可依新產(chǎn)生的排列 =次序處理而不違反任何一個(gè)期限,連續(xù)使用這種方法, 就可轉(zhuǎn)換成 且不違反任何一個(gè)期限,定理得證。 對(duì)于 且僅當(dāng)子集合 果 還沒(méi)分配處理時(shí)間,則將它分配在時(shí)間片 a處理,其中 r r,且時(shí)間片 a是空的。 仿照例 習(xí)題 提供的數(shù)據(jù)集上執(zhí)行算法 易證如果 然 如果 據(jù)定理 到 ik并且按照這個(gè)順序,可以處理 對(duì)這一序列中的任意作業(yè) 果它的時(shí)間期限是 時(shí)間片 空的,則分配之;若時(shí)間片 空,則向前找最大的非空 r時(shí)間片, 1 r 是可行解,所以一定可以找到如此時(shí)間片。故命題得證。 n=7 (, =(3,5,20,18,1,6,30) (,(1,3,4,3,2,1,2) (=(30,20,18,6,5,3,1), 對(duì)應(yīng)的期限為 (2,4,3,1,3,1,2) b=n,d(i) =,4 =4 證明如果一棵樹的所有內(nèi)部節(jié)點(diǎn)的度都為 k,則外部節(jié)點(diǎn)數(shù) 1. 證明對(duì)于滿足 n 1的正整數(shù) n,存在一棵具有 (在一棵 個(gè)節(jié)點(diǎn)的度至多為 k)。進(jìn)而證明 k. 證明:設(shè)某棵樹內(nèi)部節(jié)點(diǎn)的個(gè)數(shù)是 i,外部結(jié)點(diǎn)的個(gè)數(shù)是 n,邊的條數(shù)是 e,則有 e=i+ik=e ik=i+ (i= n 1 證明如果 n 1,則在定理 q1,生成一棵最優(yōu)的 (當(dāng)( q1, =( 3,7,8,9,15,16,18,20,23,25,28)時(shí),畫出使用這一規(guī)則所得到的最優(yōu) 3元?dú)w并樹。 通過(guò)數(shù)學(xué)歸納法證明: 對(duì)于 n=1,返回一棵沒(méi)有內(nèi)部結(jié)點(diǎn)的樹且這棵樹顯然是最優(yōu)的。 假定該算法對(duì)于( q1,,其中 m=(s+1 (s 0),都生成一棵最優(yōu)樹, 則只需證明對(duì)于 (q1,,其中 n=(s+1)+1,也能生成最優(yōu)樹即可。 不失一般性,假定 q1,算法所找到的 是 q1,生成子樹 T,設(shè) T是一棵對(duì)于( q1,的最優(yōu) 果 P的 q1,則可以用q1, 樣不增加 T的帶權(quán)外部路徑長(zhǎng)度。 因此 是在 T中如果用其權(quán)為q1+一個(gè)外部結(jié)點(diǎn)來(lái)代換 T,則所生成的樹 T是關(guān)于(T,的一棵最優(yōu)歸并樹。由歸納假設(shè),在使用其權(quán)為q1+那個(gè)外部結(jié)點(diǎn)代換了 程 T,的最優(yōu)歸并樹。因此 q1,的最優(yōu)歸并樹。 計(jì)算機(jī)算法分析 習(xí)題課 第六章 1 2 3 4 5 6 8 13 17 動(dòng)態(tài)規(guī)劃 優(yōu)性原理 遞推關(guān)系式( 右圖成立嗎?為什么? 遞推關(guān)系式( 什么對(duì)于含有負(fù)長(zhǎng)度環(huán)的圖不能成立? 解: 成立,不包含負(fù)長(zhǎng)度環(huán) 可以使節(jié)點(diǎn)間的長(zhǎng)度任意小。 修改過(guò)程 其輸出每對(duì)結(jié)點(diǎn)( i,j)間的最短路徑,這個(gè)新算法的時(shí)間和空間復(fù)雜度是多少? 回憶算法: 法 131 算法 127 算法 D(i,j)/D(j) :從節(jié)點(diǎn) 最優(yōu)路徑中 算法 j)的同時(shí)也計(jì)算了 D(j) 3 7行 計(jì)算出 D( j ) 之后,即可計(jì)算最短路徑。 9 11行 法 對(duì)矩陣進(jìn)行初始化,每個(gè)元素賦值為邊的長(zhǎng) 度(如果沒(méi)邊則賦值成 1 5行 迭代計(jì)算最短路徑長(zhǎng)度 6 12行 仿照 每次計(jì)算最短路徑的時(shí)候計(jì)算出 D(j) 再通過(guò) D(j) 就可以表示出最短路徑 k 1 to n 1 to n do j 1 to n do (i,j)A(i,k)+A(k,j) (i,j) A(i,k)+A(k,j) i,j) i,k) i 1 to n 輸出最優(yōu)路徑 j 1 to n do of i to j i ) k i, j) k 0 do k) k k, j) 析 時(shí)間復(fù)雜度 第一個(gè)循環(huán): O(第一個(gè)循環(huán): O(第一個(gè)循環(huán): O(空間復(fù)雜度 n,n) A(n,n) n,n) O(對(duì)于標(biāo)識(shí)符集( a1,a2,a3,=( 已知成功檢索概率為 P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20,不成功檢索概率為 Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20, Q(4)=1/20,用算法(i,j), R(i, j)和 C(i, j)( 0 i, j 4)。 法 P( i) P(1)=1/20, P(2)=1/5, P(3)=1/10, P(4)=1/20 Q( i) Q(0)=1/5, Q(1)=1/10, Q(2)=1/5, Q(3)=1/20, Q(4)=1/20 P( i) P(1)=1, P(2)=4, P(3)=2, P(4)=1 Q( i) Q(0)=4, Q(1)=2, Q(2)=4, Q(3)=1, Q(4)=1 證明算法 ( 在已知根 R(i, j), 0 i 1121()()() 最優(yōu)性原理并不總是對(duì)可以將其解看成是一系列決策結(jié)果的所有問(wèn)題成立。找兩個(gè)最優(yōu)性原理不成立的例子,并說(shuō)明對(duì)這兩個(gè)問(wèn)題最優(yōu)性原理為什么不成立。 多段圖問(wèn)題:路徑和改為路徑乘積并允許出現(xiàn)負(fù)數(shù) 計(jì)算機(jī)算法分析 習(xí)題課 第八章: 1、 3、 8、 9 改算法 它們只求出問(wèn)題的一個(gè)解而不是問(wèn)題的全部解 算法 8.1 n) n; : n) k 1 do (k)使得 X(k) T ( X(1), ,X(k k ( X(1), ,X(k) = X(1), ,X(k) ) 是一條抵達(dá)一答案節(jié)點(diǎn)的路徑 X(1), ,X(k) k k 1 k 1 法 8.2 k) n, X(1:n) (k) X(k) T ( X(1), ,X(k k( X(1), ,X(k)= do X(1), ,X(k) 是一條抵達(dá)一答案結(jié)點(diǎn)的路徑 X(1), ,X(k)
溫馨提示
- 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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025至2030中國(guó)網(wǎng)站易訪問(wèn)性軟件行業(yè)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢研究報(bào)告
- 2025至2030中國(guó)線激光行業(yè)發(fā)展趨勢(shì)分析與未來(lái)投資戰(zhàn)略咨詢研究報(bào)告
- 保險(xiǎn)行業(yè)數(shù)字化理賠服務(wù)數(shù)據(jù)驅(qū)動(dòng)優(yōu)化策略報(bào)告
- 基于市場(chǎng)分析的纖維素乙醇行業(yè)分析框架
- 康復(fù)科患者綜合化治療方案分享
- B3探究型學(xué)習(xí)活動(dòng)設(shè)計(jì)在電子商務(wù)教育中的心得體會(huì)
- 商業(yè)地產(chǎn)商鋪出售與品牌入駐及租金補(bǔ)貼合同范本
- 成都離婚手續(xù)辦理與婚姻關(guān)系解除協(xié)議合同
- 2025至2030高純?nèi)然鹦袠I(yè)市場(chǎng)深度研究與戰(zhàn)略咨詢分析報(bào)告
- 醫(yī)療機(jī)構(gòu)應(yīng)急保障措施
- 2025江蘇省招聘村級(jí)后備干部考試題(含答案)
- 相控陣超聲檢測(cè)技術(shù)及應(yīng)用
- 2026年高考政治一輪復(fù)習(xí):高考政治命題備考策略
- 2024年湖南省辰溪縣檔案局公開招聘試題帶答案
- 鋰離子電池安全性能優(yōu)化:針刺實(shí)驗(yàn)與失效機(jī)制分析
- 2025至2030年中國(guó)森林消防車行業(yè)市場(chǎng)全景評(píng)估及未來(lái)趨勢(shì)研判報(bào)告
- 2025生產(chǎn)與運(yùn)作管理試題及答案
- 暑假的一次冒險(xiǎn)經(jīng)歷記事作文4篇范文
- 入職預(yù)支薪資協(xié)議書
- 《中國(guó)特色社會(huì)主義理論體系的形成和發(fā)展》(課件)
- 職業(yè)技術(shù)學(xué)院嬰幼兒托育服務(wù)與管理專業(yè)人才培養(yǎng)方案
評(píng)論
0/150
提交評(píng)論