重大2015年算法設(shè)計(jì)分析 ( 第3次作業(yè) )

1、第3次作業(yè)次作業(yè)一、填空題（本大題共一、填空題（本大題共4040分，共分，共1010小題，每小題小題，每小題4分）分）1.程序的性能一般指程序的空間復(fù)雜性和______復(fù)雜性。2.矩陣連乘問(wèn)題的算法可由（）設(shè)計(jì)實(shí)現(xiàn)。3.貪心算法通過(guò)___________達(dá)成全局最優(yōu)。4.對(duì)于有n種可選擇物品的01背包問(wèn)題，其解空間由長(zhǎng)度為n的01向量組成。該解空間包含對(duì)變量的所有01賦值。當(dāng)n=2時(shí)，其解空間是：______。5.窮舉一個(gè)矩陣鏈的全部完

2、全加括號(hào)形式將會(huì)導(dǎo)致___________級(jí)的計(jì)算復(fù)雜性。6.數(shù)據(jù)的定義形式按遞歸定義，如裴波那契數(shù)列的定義：f(n)=f(n1)f(n2)f(0)=1f(1)=2.這類(lèi)遞歸問(wèn)題可轉(zhuǎn)化為遞推算法，______作為遞推的邊界條件。7.最長(zhǎng)公共子序列問(wèn)題中，c[ij]被定義為序列___________與序列_________的最長(zhǎng)公共子序列的長(zhǎng)度。8.如果存在兩個(gè)正常數(shù)c和n0對(duì)于所有的n≥n0有______則稱(chēng)g(n)是f(n)的一個(gè)下界

3、函數(shù)。舉反例證明01背包問(wèn)題若使用的算法是按照單位重量?jī)r(jià)值的非遞減次序考慮選擇的物品，即只要正在被考慮的物品裝得進(jìn)就裝入背包，則此方法不一定能得到最優(yōu)解。三、問(wèn)答題（本大題共三、問(wèn)答題（本大題共4040分，共分，共5小題，每小題小題，每小題8分）分）1.輸入三個(gè)不相同的數(shù)，求出其中的最小數(shù)。用自然語(yǔ)言描述算法。2.簡(jiǎn)述分治法在每一層遞歸上的三個(gè)步驟的具體內(nèi)容？3.設(shè)三個(gè)函數(shù)fgh分別為f(n)=100n^3n^21000g(n)=25n