[農(nóng)學(xué)]第1章緒論-資料下載頁(yè)
2024-10-16 17:48本頁(yè)面
【正文】 論： 注意引用如下關(guān)系式： n=bm， m=logbn, am=alogbn =nlogba (1) r1： ? ri 1/(1r)，由于 am=nlogba，所以， T(n)=O(nlogba)； (2)r=1： ? ri=m+1=logbn+1，由于 am =nlogba= nk，所以， T(n)=O(nk logbn)； (3)r1： ? ri =(rm+11)/(r1)=O(rm)，所以， T(n)=O(amrm)=O(bkm)=O(nk) 算法設(shè)計(jì)與分析 ? ? ? ? ? = = k k k b k k a b a n O b a n n O b a n O n T b ) ( ) log ( ) ( ) ( log 算法設(shè)計(jì)與分析 算法的后驗(yàn)分析 算法的后驗(yàn)分析（ Posteriori）也稱算法的實(shí)驗(yàn)分析，它是一種事后計(jì)算的方法，通常需要將算法轉(zhuǎn)換為對(duì)應(yīng)的程序并上機(jī)運(yùn)行。 算法設(shè)計(jì)與分析 一般步驟： 1. 明確實(shí)驗(yàn)?zāi)康? 2. 決定度量算法效率的方法 ， 為實(shí)驗(yàn)準(zhǔn)備算法的程序?qū)崿F(xiàn) 3. 決定輸入樣本，生成實(shí)驗(yàn)數(shù)據(jù) 4. 對(duì)輸入樣本運(yùn)行算法對(duì)應(yīng)的程序 ， 記錄得到的實(shí)驗(yàn)數(shù)據(jù) 5. 分析得到的實(shí)驗(yàn)數(shù)據(jù) 算法設(shè)計(jì)與分析 表格法記錄實(shí)驗(yàn)數(shù)據(jù) 129,799 113,063 91,274 78,692 67,272 53,010 39,992 24,303 11,966 次數(shù) 9000 8000 7000 6000 5000 4000 3000 2021 1000 規(guī)模 散點(diǎn)圖記錄實(shí)驗(yàn)數(shù)據(jù) 執(zhí) 行 次 數(shù) 或 時(shí) 間 問(wèn)題規(guī)模 n 算法設(shè)計(jì)與分析 作業(yè) ? 習(xí)題 1 ? 使用擴(kuò)展遞歸技術(shù)求解（ 1），使用通用分治遞推式求解（ 2） ? 12 ? 13 算法設(shè)計(jì)與分析 實(shí)驗(yàn)項(xiàng)目 —— 求最大公約數(shù) 1. 實(shí)驗(yàn)題目 求兩個(gè)自然數(shù) m和 n的最大公約數(shù) 。 2. 實(shí)驗(yàn)?zāi)康? ⑴ 復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的相關(guān)知識(shí) ， 實(shí)現(xiàn)課程間的平滑過(guò)渡； ⑵ 掌握并應(yīng)用算法的數(shù)學(xué)分析和后驗(yàn)分析方法； ⑶ 理解這樣一個(gè)觀點(diǎn)：不同的算法能夠解決相同的問(wèn)題 ， 這些算法的解題思路不同 ， 復(fù)雜程度不同 ， 解題效率也不同 。 算法設(shè)計(jì)與分析 3. 實(shí)驗(yàn)要求 ⑴ 至少設(shè)計(jì)出三個(gè)版本的求最大公約數(shù)算法； ⑵ 對(duì)所設(shè)計(jì)的算法采用大 O符號(hào)進(jìn)行時(shí)間復(fù)雜性分析； ⑶ 上機(jī)實(shí)現(xiàn)算法 ， 并用計(jì)數(shù)法測(cè)算算法的運(yùn)行時(shí)間； ⑷ 通過(guò)分析對(duì)比 ， 得出自己的結(jié)論 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1