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

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

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

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