acm算法教程(存儲(chǔ)版)
【正文】 算法的五大特性： ⑴ 輸入：一個(gè)算法有零個(gè)或多個(gè)輸入。 算法設(shè)計(jì)與分析 淮海工學(xué)院 歐幾里德算法 m n r 例：歐幾里德算法 —— 輾轉(zhuǎn)相除法求兩個(gè)自然數(shù) m 和 n 的最大公約數(shù) 算法設(shè)計(jì)與分析 淮海工學(xué)院 算法的描述方法 ⑴ 自然語(yǔ)言 優(yōu)點(diǎn)：容易理解 缺點(diǎn)：冗長(zhǎng)、二義性 使用方法：粗線條描述算法思想 注意事項(xiàng)：避免寫成自然段 算法設(shè)計(jì)與分析 淮海工學(xué)院 ① 輸入 m 和 n； ② 求 m除以 n的余數(shù) r； ③ 若 r等于 0， 則 n為最大公約數(shù) ， 算法結(jié)束； 否則執(zhí)行第 ④ 步； ④ 將 n的值放在 m中 ， 將 r的值放在 n中； ⑤ 重新執(zhí)行第 ② 步 。 優(yōu)點(diǎn)：表達(dá)能力強(qiáng)，抽象性強(qiáng)，容易理解 使用方法： 7 177。 i++) for (j=1。 } 算法設(shè)計(jì)與分析 淮海工學(xué)院 ?最好情況： ?最差情況： ?平均情況：已知輸入數(shù)據(jù)是如何分布的， 通常假設(shè)等概率分布 結(jié)論：如果問(wèn)題規(guī)模相同，時(shí)間代價(jià)與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、最壞情況、平均情況。 ?關(guān)鍵：根據(jù)遞歸過(guò)程建立遞推關(guān)系式 ， 然后求解這個(gè)遞推關(guān)系式 。 算法設(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é)論 。 } 算法設(shè)計(jì)與分析 淮海工學(xué)院 非遞歸算法分析的一般步驟： 1. 決定用哪個(gè) （ 或哪些 ） 參數(shù)作為算法問(wèn)題規(guī)模的度量 2. 找出算法中的基本語(yǔ)句 3. 檢查基本語(yǔ)句的執(zhí)行次數(shù)是否只依賴于問(wèn)題規(guī)模 4. 建立基本語(yǔ)句執(zhí)行次數(shù)的求和表達(dá)式 5. 用漸進(jìn)符號(hào)表示這個(gè)求和表達(dá)式 ?關(guān)鍵：建立一個(gè)代表算法運(yùn)行時(shí)間的求和表達(dá)式 ， 然后用漸進(jìn)符號(hào)表示這個(gè)求和表達(dá)式 。 i++) if (A[i]= =k) break。 歐幾里德算法 算法設(shè)計(jì)與分析 淮海工學(xué)院 算法設(shè)計(jì)的一般過(guò)程 1．理解問(wèn)題 2．預(yù)測(cè)所有可能的輸入 3. 在精確解和近似解間做選擇 4. 確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu) 5． 算法設(shè)計(jì)技術(shù) 6．描述算法 7．跟蹤算法 （人腦執(zhí)行） 8．分析算法的效率 9．根據(jù)算法編寫代碼 算法設(shè)計(jì)與分析 淮海工學(xué)院 重要的問(wèn)題類型 1.
語(yǔ)文相關(guān)推薦
鄂ICP備17016276號(hào)-1