下載本文檔
版權(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 個(gè)人生活應(yīng)急借款協(xié)議2024版版A版
- 二零二五年度茶樓經(jīng)營(yíng)權(quán)及特色茶飲配方轉(zhuǎn)讓合同3篇
- 2024石子供應(yīng)合同:違約責(zé)任與爭(zhēng)議解決
- 《人民代表大會(huì):我國(guó)的國(guó)家權(quán)力機(jī)關(guān)》說(shuō)課稿
- 2025年度私立醫(yī)院牙科技術(shù)合作承包合同范本3篇
- Unit 3 Keep Fit Section B Project說(shuō)課稿 -2024-2025學(xué)年人教版(2024)七年級(jí)英語(yǔ)下冊(cè)
- 2024版銷售推廣代理協(xié)議書
- 專業(yè)工程資金貸借協(xié)議精簡(jiǎn)版版B版
- 2025年離婚后房產(chǎn)分割及共有權(quán)處理合同4篇
- 二年級(jí)數(shù)學(xué)計(jì)算題專項(xiàng)練習(xí)
- 三年級(jí)數(shù)學(xué)寒假作業(yè)每日一練30天
- 二年級(jí)數(shù)學(xué)上冊(cè)100道口算題大全 (每日一套共26套)
- 浙教版初中科學(xué)八下《表示元素的符號(hào)》課件
- 總住院醫(yī)師管理制度
- 八年級(jí)上冊(cè)歷史 第二單元 社會(huì)主義制度的建立與社會(huì)主義建設(shè)的探索
- DB31T 360-2020 住宅物業(yè)管理服務(wù)規(guī)范
- 園林綠化工程大樹移植施工方案
- 應(yīng)收賬款最高額質(zhì)押擔(dān)保合同模版
- 基于新型光彈性實(shí)驗(yàn)技術(shù)的力學(xué)實(shí)驗(yàn)教學(xué)方法探索
- 訴前車輛保全申請(qǐng)書(5篇)
- 醫(yī)院后勤保障管理組織架構(gòu)圖
評(píng)論
0/150
提交評(píng)論