acm算法教程(參考版)
2024-08-15 09:26本頁面
【正文】 算法設(shè)計與分析 淮海工學(xué)院 3. 實驗要求 ⑴ 至少設(shè)計出三個版本的求最大公約數(shù)算法； ⑵ 對所設(shè)計的算法采用大 O符號進(jìn)行時間復(fù)雜性分析； ⑶ 上機(jī)實現(xiàn)算法 ， 并用計數(shù)法和計時法分別測算算法的運(yùn)行時間； ⑷ 通過分析對比 ， 得出自己的結(jié)論 。 算法設(shè)計與分析 淮海工學(xué)院 一般步驟： 1. 明確實驗?zāi)康? 2. 決定度量算法效率的方法 ， 為實驗準(zhǔn)備算法的程序?qū)崿F(xiàn) 3. 決定輸入樣本，生成實驗數(shù)據(jù) 4. 對輸入樣本運(yùn)行算法對應(yīng)的程序 ， 記錄得到的實驗數(shù)據(jù) 5. 分析得到的實驗數(shù)據(jù) 算法設(shè)計與分析 淮海工學(xué)院 表格法記錄實驗數(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ī)模 散點圖記錄實驗數(shù)據(jù) 執(zhí) 行 次 數(shù) 或 時 間 問題規(guī)模 n 算法設(shè)計與分析 淮海工學(xué)院 實驗項目 —— 求最大公約數(shù) 1. 實驗題目 求兩個自然數(shù) m和 n的最大公約數(shù) 。 + + + = + + + = + + = + = L 算法設(shè)計與分析 淮海工學(xué)院 3. 通用分治遞推式 大小為 n的原問題分成若干個大小為 n/b的子問題，其中 a個子問題需要求解，而 k是合并各個子問題的解需要的工作量。 ?關(guān)鍵：根據(jù)遞歸過程建立遞推關(guān)系式 ， 然后求解這個遞推關(guān)系式 。 } 算法設(shè)計與分析 淮海工學(xué)院 非遞歸算法分析的一般步驟： 1. 決定用哪個 （ 或哪些 ） 參數(shù)作為算法問題規(guī)模的度量 2. 找出算法中的基本語句 3. 檢查基本語句的執(zhí)行次數(shù)是否只依賴于問題規(guī)模 4. 建立基本語句執(zhí)行次數(shù)的求和表達(dá)式 5. 用漸進(jìn)符號表示這個求和表達(dá)式 ?關(guān)鍵：建立一個代表算法運(yùn)行時間的求和表達(dá)式 ， 然后用漸進(jìn)符號表示這個求和表達(dá)式 。 i++) if (a[i]min) min=a[i]。 for (i=1。 } 算法設(shè)計與分析 淮海工學(xué)院 ?最好情況： ?最差情況： ?平均情況：已知輸入數(shù)據(jù)是如何分布的， 通常假設(shè)等概率分布 結(jié)論：如果問題規(guī)模相同，時間代價與輸入數(shù)據(jù)有關(guān)，則需要分析最好情況、最壞情況、平均情況。 i++) if (A[i]= =k) break。 算法設(shè)計與分析 淮海工學(xué)
語文相關(guān)推薦
鄂ICP備17016276號-1