算法設(shè)計基本方法ppt課件(參考版)
2025-05-15 12:54本頁面
【正文】 2）下界函數(shù) 定義 如果存在正常數(shù) c1， c2和 n0，對于所有的 n≥n 0，有 c1|g(n)| ≤|f(n)| ≤ c 2|g(n)| 則記作 含義： ? 算法在最好和最壞情況下的計算時間就一個 常數(shù)因子 范圍內(nèi)而言是相同的。所以 g(n)是計算時間 f(n)的一個 下界函數(shù) 。 ? 要想在順序處理機(jī)上擴(kuò)大所處理問題的規(guī)模，有效的途徑 是 降低算法的計算復(fù)雜度 ，而不是（僅僅依靠）提高計算 機(jī)的速度。 典型的計算時間函數(shù)曲線 ? 一般認(rèn)識 ? 當(dāng)數(shù)據(jù)集的規(guī)模很大時，要在現(xiàn)有的計算機(jī)系統(tǒng)上運(yùn)行 具有比 Ο(nlogn)復(fù)雜度還高的算法是比較困難的。 多項(xiàng)式時間算法 和 指數(shù)時間算法 ? 多項(xiàng)式時間算法 ：可用多項(xiàng)式（函數(shù)）對其計算時間限界 的算法。 n=2048：分別需要 4194304和 22528次運(yùn)算。 計算時間的 數(shù)量級的大小對算法有 決定性 的影響 例：假設(shè)解決同一個問題的兩個算法，它們都有 n個輸入 , 計算時間的數(shù)量級分別是 n2和 nlogn。 例：假如求解同一個問題的三個算法分別具有 n， n2 ， n3數(shù)量級。 ? 數(shù)量級 —— 衡量 工作量 的“ 大小 ”的一種測度，通過 f(n)的上界函數(shù) g(n)確定 ? 語句的數(shù)量級 ：語句的執(zhí)行次數(shù) 例： 1， n ， n2 ? 算法的數(shù)量級 ：算法所包含的所有語句的執(zhí)行次數(shù)之和。 f(n)的數(shù)量級就是 g(n)。 ?1）上界函數(shù) 定義 1 如果存在兩個正常數(shù) c和 n0，對于所有的 n≥n 0，有 |f(n)| ≤ c|g(n)| 則記作 f(n) = Ο(g(n)) 含義： ? 如果算法用 n值不變的同一類數(shù)據(jù)在某臺機(jī)器上運(yùn)行時，所用的時間總是小于 |g(n)|的一個常數(shù)倍。是與工作量有關(guān)、而 與機(jī)器及語言無 關(guān) 的函數(shù)。 ? f(n)表示算法的“實(shí)際”執(zhí)行時間 —與機(jī)器及語言有關(guān) 。j++) x = x +y (a) (b) (c) 分析： (a)： x=x+y執(zhí)行了 1次 (b)： x=x+y執(zhí)行了 n次 (c)： x=x+y執(zhí)行了 n2次 ? 限界函數(shù)的表示 就 計算時間 而言，事前分析階段求得算法在工作量 上的算法規(guī)模 n的 函數(shù) 稱為限界函數(shù)，記為： g(n) 限界函數(shù)以算法中主要運(yùn)算單元為基本運(yùn)算統(tǒng)計運(yùn)算次數(shù)的數(shù)量級 ★ g(n)的一般形式：關(guān)于 n的簡單函數(shù)式 g(n)用以限界，因此只采用所得到計算次數(shù)的最高次項(xiàng)表示：隨著 n（規(guī)模）的增大，多項(xiàng)式函數(shù)式的 最高次 項(xiàng)的變化能夠最顯著的反映整個多項(xiàng)式的變化 ★ 不同的算法， g(n)的具體形式是不同的，常用的限界函數(shù)有： 1； logn； n； nlogn； n2； n3； nm ； 2n； n??； nn等 2）事后測試 ? 目的：運(yùn)行程序，統(tǒng)計執(zhí)行實(shí)際耗費(fèi)的準(zhǔn)確的時間與空間，與事前分析的結(jié)論進(jìn)行比較，驗(yàn)證先前的分析結(jié)論 ——包括正確性、執(zhí)行性能等，比較、優(yōu)化所設(shè)計的算法。i++) x = x + y for (j=0。i++) for (i=0。 例： x=x+y for (i=0。 ? 如何給出反映算法特性的描述 ？ 統(tǒng)計算法中各種運(yùn)算的執(zhí)行情況，包括： ? 引用了哪些運(yùn)算 ? 每種運(yùn)算被執(zhí)行的次數(shù) ? 該種運(yùn)算執(zhí)行一次所花費(fèi)的時間等。 ?事后測試 ：將算法編制成程序后實(shí)際放到計算機(jī)上運(yùn)行， 收集其執(zhí)行時間和空間占用等統(tǒng)計資料，進(jìn)行 分析判斷 ——直接與物理實(shí)現(xiàn)有關(guān)。 基本運(yùn)算 :x與數(shù)組元素的比較。 算法分析 ? “好”的算法應(yīng)當(dāng)達(dá)到以下指標(biāo) ? 正確性 (Correctness):算法應(yīng)當(dāng)滿足具體問題的需求 ? 可讀性 (Readability):算法是連接數(shù)學(xué)模型和程序的橋梁 ,可讀性好有助于人對算法的理解 ? 健壯性 (Robustness):算法對于異常情況有充分
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1