acm算法教程-資料下載頁(yè)
2025-08-04 09:26本頁(yè)面
【正文】 2 ( 2 ) ( n n n T n n n n T n n n T n n T n T k k k + 180。 + + + = + + + = + + = + = L 算法設(shè)計(jì)與分析 淮海工學(xué)院 3. 通用分治遞推式 大小為 n的原問(wèn)題分成若干個(gè)大小為 n/b的子問(wèn)題，其中 a個(gè)子問(wèn)題需要求解，而 k是合并各個(gè)子問(wèn)題的解需要的工作量。 ? ? ? + = = 1 ) ( 1 ) ( n b n aT n c n T k ? ? ? ? ? = = 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ì)與分析 淮海工學(xué)院 算法的后驗(yàn)分析 算法的后驗(yàn)分析（ Posteriori）也稱(chēng)算法的實(shí)驗(yàn)分析，它是一種事后計(jì)算的方法，通常需要將算法轉(zhuǎn)換為對(duì)應(yīng)的程序并上機(jī)運(yùn)行。 算法設(shè)計(jì)與分析 淮海工學(xué)院 一般步驟： 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ì)與分析 淮海工學(xué)院 表格法記錄實(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 2022 1000 規(guī)模 散點(diǎn)圖記錄實(shí)驗(yàn)數(shù)據(jù) 執(zhí) 行 次 數(shù) 或 時(shí) 間 問(wèn)題規(guī)模 n 算法設(shè)計(jì)與分析 淮海工學(xué)院 實(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ì)與分析 淮海工學(xué)院 3. 實(shí)驗(yàn)要求 ⑴ 至少設(shè)計(jì)出三個(gè)版本的求最大公約數(shù)算法； ⑵ 對(duì)所設(shè)計(jì)的算法采用大 O符號(hào)進(jìn)行時(shí)間復(fù)雜性分析； ⑶ 上機(jī)實(shí)現(xiàn)算法 ， 并用計(jì)數(shù)法和計(jì)時(shí)法分別測(cè)算算法的運(yùn)行時(shí)間； ⑷ 通過(guò)分析對(duì)比 ， 得出自己的結(jié)論 。
語(yǔ)文相關(guān)推薦
鄂ICP備17016276號(hào)-1