【正文】 是n的某一函數(shù)，T(n)稱為這一算法的“時間復(fù)雜性”?！按驩記法”：基本參數(shù) n表示問題實例的規(guī)模，把復(fù)雜性或運行時間表達為n的函數(shù)。“O”表示量級 (order)，允許使用“=”代替“≈”，如n2+n+1 =Ο(n2)，所以正確答案選B；具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(3)算法的時間復(fù)雜性T(n)，可以通過計算算法基本語句的執(zhí)行次數(shù)來獲得。分析下列程序的時間復(fù)雜性。(10) K = 0； (20) I = 2；(30) While (I=8)(40) { K = K + I； (50) I = I + 2；}該程序時間復(fù)雜性表達正確的是_________。(A)O(n)；(B)O(1)；(C)O(n2)；(D)O(n!)；答案：B解釋：本題考查時間復(fù)雜性，和大“O”記法；具體分析如下：K = 0； 1次I = 2； 1次While (I=8) 8次{ K = K + I； 8次I = I + 2； 8次} T(n)=1+1+8 3= O(1)，所以答案選B； 具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(4)算法的時間復(fù)雜性T(n)，可以通過計算算法基本語句的執(zhí)行次數(shù)來獲得。分析下列程序的時間復(fù)雜性。(10) sum=0； (20) For(i=1。 i=n。 i++)(30) For(j=1。 j=n。 j++)(40) For(k=1。 k=j。 k++)(50) sum=sum+1；該程序時間復(fù)雜性表達正確的是_________。(A)O(n)；(B)O(n2)；(C)O(n3)；(D)上述都不對；答案：C解釋：本題考查時間復(fù)雜性，和大“O”記法；具體分析如下：(10) sum=0； 1次(20) For(i=1。 i=n。 i++) n次(30) For(j=1。 j=n。 j++) n2次(40) For(k=1。 k=j。 k++) n3次(50) sum=sum+1； n3次T(n) = 2 n3 + n2 + n + 1 = O(n3)，所以正確答案選C；具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(5)算法的時間復(fù)雜性T(n)，可以通過計算算法基本語句的執(zhí)行次數(shù)來獲得。分析下列程序的時間復(fù)雜性。(10) sum=0； (20) For(i=1。 i=n。 i++)(30) For(j=1。 j=n。 j++)(40) For(k=1。 k=5。 k++)(50) sum=sum+1；該程序時間復(fù)雜性表達正確的是_________。(A)O(n)；(B)O(n2)；(C)O(n3)；(D)上述都不對；答案：B解釋：本題考查時間復(fù)雜性，和大“O”記法；具體分析如下：(10) sum=0； 1次(20) For(i=1。 i=n。 i++) n次(30) For(j=1。 j=n。 j++) n2次(40) For(k=1。 k=5。 k++) 5 n2次(50) sum=sum+1； 5 n2次T(n)= 11n2 + n + 1 = O(n2)，所以正確答案選B； 具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(6)閱讀下面的程序，其時間復(fù)雜度為_________?A. O(1) B. O(n) C. O(n2) D. O(n*log n)int index = 5。int condition=1。if (condition==1) then index++。else index； for i = 1 to 100 for j = 1 to 200 index=index+2。答案：A解釋： 本題考查時間復(fù)雜性，和大“O”記法；具體分析如下：int index = 5。 1次int condition=1。 1次if (condition==1) then 1次 index++。 1次else index； for i = 1 to 100 100次 for j = 1 to 200 200100次 index=index+2。 200100次 所以T(n)=O(1)，正確答案選A； 具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件； (7)為什么要評估算法的復(fù)雜性？下列說法不正確的是_________。(A)當(dāng)算法的時間復(fù)雜性量級為多項式函數(shù)時，計算機是能夠完成計算的；(B)當(dāng)算法的時間復(fù)雜性量級為非多項式函數(shù)時，如指數(shù)函數(shù)、階乘函數(shù)時，計算機是不能夠完成計算的；(C)當(dāng)算法的時間復(fù)雜性量級為非多項式函數(shù)時，如指數(shù)函數(shù)、階乘函數(shù)時，對于大規(guī)模問題，計算機是不能夠完成計算的；(D)上述說法有不正確的；答案：B解釋：本題考查算法分析與計算復(fù)雜性；當(dāng)算法的時間復(fù)雜度的表示函數(shù)是一個多項式時，如O(n2)時，則計算機對于大規(guī)模問題是可以處理的。當(dāng)算法的時間復(fù)雜度是用指數(shù)函數(shù)表示時，如O(2n)，當(dāng)n很大（如10000）時計算機是無法處理的，在計算復(fù)雜性中將這一類問題被稱為難解性問題。所以對于B的表達，只有當(dāng)n很大時，屬于大規(guī)模問題時，計算機才不能完成，表達不精確，所以正確答案為B； 具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(*8)算法的時間復(fù)雜性T(n)，可以通過評估算法基本語句的執(zhí)行次數(shù)來獲得。分析下列算法的時間復(fù)雜性。Start of the algorithm(算法開始)(1) 輸入結(jié)點的數(shù)目n； (2) 當(dāng)前最短路徑Path設(shè)為空，當(dāng)前最短距離Dtemp設(shè)為最大值；注：一個路徑是n個結(jié)點的一個組合，任何一個結(jié)點在路經(jīng)中不能重復(fù)出現(xiàn) (3) 組合一條新路徑NewPath并計算該路徑的距離D； (4) 如果DDtemp 則Path = NewPath，且Dtemp = D；(5) 如果所有路徑組合完畢，則結(jié)束；否則轉(zhuǎn)第(3)步繼續(xù)執(zhí)行； (6) 輸出Path及Dtemp； End of the algorithm(算法結(jié)束) 該算法的時間復(fù)雜性表達正確的是_________。(A)O(3n)；(B)O(n2)；(C)O(n3)；(D)O(n!)； (E)上述都不對；答案：D解釋： 本題考查時間復(fù)雜性，和大“O”記法；由以上步驟可知，由于輸入結(jié)點的數(shù)目為n，總共有n！種組合方式，所以時間復(fù)雜性應(yīng)為O(n!)；正確答案選D。 具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；(*9)分析下列算法的時間復(fù)雜性。Start of the Algorithm(1) S[1]=1。 Sum=0。 初始化距離數(shù)組D[n][n]。 /*I層的循環(huán)，即下列步驟為每次找出一個城市，I從2到n，即從找出第2個城市一直到找出第n個城市(2) I=2。/*K層的循環(huán)，即下列步驟為從所有未訪問過的城市中查找距離S[I1]最近的城市j，K依然從2到n尋找(3) K=2。(4) 將Dtemp設(shè)為一個大數(shù)(比所有兩個城市之間的距離都大)/*L層的循環(huán)，即下列步驟為判斷一個城市是否已被訪問過，如果已被訪問，則跳過該城市，尋找新的城市，L從1到I1，因為已經(jīng)有I1個城市被訪問過。(5) L=1；(6) 如果S[L]==K，轉(zhuǎn)步驟(10)； (7) L=L+1；(8) 如果LI，轉(zhuǎn)步驟(6)；/*L層的循環(huán)結(jié)束(9) 如果D[K,S[I1]]Dtemp，j=K，Dtemp＝D[K,S[I1]]；(10) K=K+1。(11) 如果K=N，轉(zhuǎn)步驟(5)。/*K層的循環(huán)結(jié)束(12) S[I]=j。(13) Sum=Sum+Dtemp。(14) I=I+1。(15) 如果I=N，轉(zhuǎn)步驟(3)，否則，轉(zhuǎn)步驟(16)。/*I層的循環(huán)結(jié)束(16) Sum=Sum+D[1, j]；(17) 逐個輸出S[N]中的全部元素。(18) 輸出Sum。End of the Algorithm該算法的時間復(fù)雜性表達正確的是_________。(A)O(3n)；(B)O(n2)；(C)O(n3)；(D)O(n!)； (E)上述都不對；答案：C解釋： 本題考查TSP算法和時間復(fù)雜性；TSP問題貪心算法的復(fù)雜性：粗略看是一個關(guān)于n的三重循環(huán)，即復(fù)雜度為n3級別。所以時間復(fù)雜度是O(n3)，正確答案選C；具體內(nèi)容請參考課堂視頻“高級問題初探: 算法分析與計算復(fù)雜性”和第七章課件；，回答下列問題：(1)下列說法不正確的是_________。(A)算法類問題求解首先要進行數(shù)學(xué)建模，即用數(shù)學(xué)語言對問題進行抽象；(B)一個問題，進行了數(shù)學(xué)建模后，可以通過模型的一些性質(zhì)的分析判斷該問題是否有解；在有解的情況下，再設(shè)計算法進行求解，否則則可能做的是無用功！ (C)一個問題，進行了數(shù)學(xué)建模后，可以依據(jù)數(shù)學(xué)的一些求解方法，設(shè)計出讓計算機求解的算法。 (D)一個問題，雖然進行了數(shù)學(xué)建模但可以不依據(jù)數(shù)學(xué)求解方法，設(shè)計出讓計算機求解的算法； (E)上述說法有不正確的。答案：E解釋： 本題考查算法問題求解的基本步驟；求解一個算法問題，首先要進行數(shù)學(xué)建模，用數(shù)學(xué)語言對問題進行抽象，A正確；進行數(shù)學(xué)建模后，要判斷該問題是否有解，所以B也正確；之后要根據(jù)數(shù)學(xué)模型，設(shè)計出求解的算法，C正確；對于一個數(shù)學(xué)模型，我們可以用不同的數(shù)學(xué)方法設(shè)計出不同的解法，所以D也正確；綜上所述，正確答案選E； 具體內(nèi)容請參考第七章所有視頻和課件；(2)對于算法類問題求解，下列說法正確的是_________。(A)一般而言，算法類問題求解包括數(shù)學(xué)建模、算法策略設(shè)計、算法的數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)設(shè)計三個基本步驟；(B)一般而言，算法類問題求解包括數(shù)學(xué)建模、算法策略設(shè)計、算法的數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)設(shè)計、算法的正確性與復(fù)雜性分析四個基本步驟； (C)一般而言，算法類問題求解包括數(shù)學(xué)建模、算法策略設(shè)計、算法的數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)設(shè)計、算法的程序?qū)崿F(xiàn)、算法的正確性與復(fù)雜性分析五個基本步驟； (D)上述說法都正確。答案：C解釋： 本題考查算法問題求解的基本步驟；對于算法類問題求解主要包括數(shù)學(xué)建模、算法策略設(shè)計、算法的數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)設(shè)計、算法的程序?qū)崿F(xiàn)、算法的正確性與復(fù)雜性分析五個基本步驟，所以C正確； 具體內(nèi)容請參考課堂視頻“算法與算法類問題求解”和第七章課件；