一復(fù)雜性分析初步習(xí)題參考_第1頁(yè)
一復(fù)雜性分析初步習(xí)題參考_第2頁(yè)
一復(fù)雜性分析初步習(xí)題參考_第3頁(yè)
一復(fù)雜性分析初步習(xí)題參考_第4頁(yè)
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、習(xí)題一復(fù)雜性剖析初步試確立下述程序的履行步數(shù),該函數(shù)實(shí)現(xiàn)一個(gè)mn矩陣與一個(gè)np矩陣之間的乘法:矩陣乘法運(yùn)算templatevoidMult(T*a,T*b,intm,intn,intp)語(yǔ)句s/e頻次總步數(shù)templatevoidMult(T*a,T*b,intm,intn,intp)000for(inti=0;im;i+)1m+1m+1for(intj=0;jp;j+)1m*(p+1)m*p+mTsum=0;1m*pm*pfor(intk=0;kn;k+)1m*p*(n+1)m*p*n+m*pSum+=aik*bkj;1m*p*nm*p*nCij=sum;1m*pm*p總計(jì)2*m*p*n+4

2、*m*p+2*m+13(n1)明以下不等式不建立:21).10n29O(n);2).n2logn(n2);4證明:當(dāng)且僅當(dāng)limfngn0時(shí),f(n)o(g(n)。n5.下邊那些規(guī)則是正確的為何1).f(n)O(F(n),g(n)O(G(n)f(n)/g(n)O(F(n)/G(n);錯(cuò)2).f(n)O(F(n),g(n)O(G(n)f(n)/g(n)(F(n)/G(n);錯(cuò)3).f(n)O(F(n),g(n)O(G(n)f(n)/g(n)(F(n)/G(n);錯(cuò)4).f(n)(F(n),g(n)(G(n)f(n)/g(n)(F(n)/G(n);錯(cuò)5).f(n)(F(n),g(n)(G(n)f(

3、n)/g(n)(F(n)/G(n)。錯(cuò)6).f(n)(F(n),g(n)(G(n)f(n)/g(n)(F(n)/G(n)對(duì)依據(jù)漸進(jìn)階從低到高的次序擺列以下表達(dá)式:4n2,logn,3n,20n,n2/3,n!次序:lognn2/320n4n23nn!1)假定某算法在輸入規(guī)模是n時(shí)為T(n)3*2n.在某臺(tái)計(jì)算機(jī)上實(shí)現(xiàn)并達(dá)成該算法的時(shí)間是t秒.現(xiàn)有另一臺(tái)計(jì)算機(jī),其運(yùn)轉(zhuǎn)速度為第一臺(tái)的64倍,那么,在這臺(tái)計(jì)算機(jī)上用同一算法在t秒內(nèi)能解決規(guī)模為多大的問(wèn)題規(guī)模時(shí)間復(fù)雜度(步數(shù))原運(yùn)轉(zhuǎn)速度(時(shí)間/每步)總時(shí)間nT(n)3*2nt0t關(guān)系式為時(shí)間復(fù)雜度(計(jì)算步數(shù))*運(yùn)轉(zhuǎn)速度(時(shí)間/每步)=運(yùn)轉(zhuǎn)所需時(shí)間,即T

4、(n)*t0t解:設(shè)在新機(jī)器上t秒內(nèi)能解決規(guī)模為m的問(wèn)題,時(shí)間復(fù)雜度變成T(m)3*2m,因?yàn)樾聶C(jī)器運(yùn)轉(zhuǎn)速度提升64倍,則運(yùn)轉(zhuǎn)速度變成t新t0,64由關(guān)系式T(n)*t0t,T(m)*t新t,得3*2n*t0t,3*2m*t0t64解得mn62)若上述算法改良后,新算法的計(jì)算復(fù)雜度為T(n)n2,則在新機(jī)器上用秒時(shí)間能解決輸入規(guī)模為多大的問(wèn)題設(shè)在新機(jī)器上用t秒時(shí)間能解決輸入規(guī)模為N的問(wèn)題,則因?yàn)樾聫?fù)雜度T新(N)N2,新機(jī)器的運(yùn)轉(zhuǎn)速度為t新t0,64代入關(guān)系式T新(N)*t新t,得N2*t0t3*2n*t0,64解得N832n3)若進(jìn)一步改良算法,最新的算法的時(shí)間復(fù)雜度為T(n)8,其他條件不

5、變,在新機(jī)器上運(yùn)轉(zhuǎn),在t秒內(nèi)可以解決輸入規(guī)模為多大的問(wèn)題設(shè)可解決的最大時(shí)間復(fù)雜度為Tmax,則Tmax*t0t3*2n*t064可解決的最大時(shí)間復(fù)雜度為T192*2n,(n為原始的輸入規(guī)模)。max因?yàn)門(n)8Tmax,且T(n)為常數(shù)不隨輸入規(guī)模n變化,因此隨意規(guī)模的n都可在t秒內(nèi)解決。8.Fibonacci數(shù)有遞推關(guān)系:1,n0F(n)1,n1F(n1)F(n2),n1試求出F(n)的表達(dá)式。解:方法一:當(dāng)n1時(shí),由遞推公式F(n)F(n1)F(n2)得特點(diǎn)方程為x2x1解得x115,x21522則可設(shè)F(n)c1x1nc2x2n由F(2)2,F(xiàn)(3)3,解得c115,c2152525故F(n)115n115n1,5()()22當(dāng)n0,1時(shí),帶入考證亦建立。故F(n)1(15)n1(15)n152

溫馨提示

  • 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ì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論